Submission #1650381
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
using pi = pair<int,int>;
const int N = 100000;
const ll INF = LLONG_MAX/3;
vector<int> G[N];
vector<int> ew;
void dfs(int v)
{
ew.pb(v);
for(int c:G[v]) dfs(c);
ew.pb(v);
}
int main()
{
int n;
scanf(" %d", &n);
vector<int> a(n);
rep(i,n) scanf(" %d", &a[i]);
vector<bool> candidate(n,true);
rep(i,n-1)
{
int s,t;
scanf(" %d %d", &s, &t);
G[s].pb(t);
candidate[t] = false;
}
int root = 0;
rep(i,n)if(candidate[i]) root = i;
dfs(root);
vector<ll> val(n,INF);
set<int> v;
vector<int> ct(n);
rep(i,ew.size())
{
int id = ew[i];
if(ct[id]==0)
{
auto itr = v.lower_bound(a[id]);
if(itr!=v.end())
{
int x = *itr;
if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
}
if(itr!=v.begin())
{
--itr;
int x = *itr;
if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
}
}
else v.insert(a[id]);
++ct[id];
}
v.clear();
reverse(all(ew));
ct = vector<int>(n,0);
rep(i,ew.size())
{
int id = ew[i];
if(ct[id]==0)
{
auto itr = v.lower_bound(a[id]);
if(itr!=v.end())
{
int x = *itr;
if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
}
if(itr!=v.begin())
{
--itr;
int x = *itr;
if(abs(a[id]-x)<abs(val[id]-x)) val[id] = x;
}
}
else v.insert(a[id]);
++ct[id];
}
rep(i,n) printf("%lld\n", val[i]==INF?-1:val[i]);
return 0;
}
Submission Info
Submission Time |
|
Task |
I - 支配と友好 |
User |
imulan |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2348 Byte |
Status |
WA |
Exec Time |
171 ms |
Memory |
17708 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:30:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d", &n);
^
./Main.cpp:32:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,n) scanf(" %d", &a[i]);
^
./Main.cpp:38:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d", &s, &t);
^
Judge Result
Set Name |
All |
Score / Max Score |
0 / 200 |
Status |
|
Set Name |
Test Cases |
All |
sample01, sample02, sample03, binary00, binary01, binary02, binary03, hand00, line00, line01, line02, random00, random01, random02, random03, random04, random05, random06, random07, random08, sample01, sample02, sample03, star00, star01, star02, ternary00, ternary01, ternary02, ternary03, thin00, thin01, thin02, thin03, thin04, thin05, thin06, thin07, uniform00, uniform01, uniform02, uniform03, uniform04, uniform05, uniform06 |
Case Name |
Status |
Exec Time |
Memory |
binary00 |
AC |
73 ms |
7156 KB |
binary01 |
WA |
106 ms |
7412 KB |
binary02 |
WA |
153 ms |
11968 KB |
binary03 |
WA |
150 ms |
12204 KB |
hand00 |
AC |
112 ms |
15916 KB |
line00 |
AC |
69 ms |
13428 KB |
line01 |
AC |
95 ms |
13556 KB |
line02 |
AC |
133 ms |
17708 KB |
random00 |
AC |
62 ms |
7160 KB |
random01 |
AC |
70 ms |
7288 KB |
random02 |
AC |
85 ms |
7288 KB |
random03 |
WA |
104 ms |
7544 KB |
random04 |
WA |
141 ms |
10092 KB |
random05 |
WA |
149 ms |
11664 KB |
random06 |
WA |
149 ms |
11972 KB |
random07 |
WA |
150 ms |
12080 KB |
random08 |
WA |
160 ms |
12208 KB |
sample01 |
WA |
3 ms |
2560 KB |
sample02 |
AC |
3 ms |
2560 KB |
sample03 |
WA |
3 ms |
2560 KB |
star00 |
AC |
56 ms |
6008 KB |
star01 |
AC |
92 ms |
6264 KB |
star02 |
WA |
141 ms |
10928 KB |
ternary00 |
AC |
67 ms |
6644 KB |
ternary01 |
WA |
104 ms |
6900 KB |
ternary02 |
WA |
146 ms |
11460 KB |
ternary03 |
WA |
149 ms |
11692 KB |
thin00 |
WA |
72 ms |
9460 KB |
thin01 |
WA |
70 ms |
8180 KB |
thin02 |
WA |
112 ms |
9844 KB |
thin03 |
WA |
108 ms |
8436 KB |
thin04 |
WA |
171 ms |
14276 KB |
thin05 |
WA |
149 ms |
12992 KB |
thin06 |
WA |
156 ms |
14508 KB |
thin07 |
WA |
153 ms |
13228 KB |
uniform00 |
WA |
155 ms |
11312 KB |
uniform01 |
WA |
143 ms |
11632 KB |
uniform02 |
WA |
157 ms |
11380 KB |
uniform03 |
WA |
153 ms |
11276 KB |
uniform04 |
WA |
155 ms |
11108 KB |
uniform05 |
WA |
149 ms |
11104 KB |
uniform06 |
WA |
145 ms |
10976 KB |