Submission #139670
Source Code Expand
#include<cstdio> #include<algorithm> #include<vector> #include<set> #define rep(i,n) for(int i = 0; i < n; i++) #define rng(a) a.begin(),a.end() #define pb push_back using namespace std; typedef long long int ll; typedef pair<int,int> P; typedef vector<int> vi; const int MX = 100005, INF = 2000010000; int n, root; vi ch[MX]; bool flag[MX]; int c[MX], ans[MX]; set<int> t; inline void up(int v, int x){ int d = abs(ans[v]-c[v]) - abs(x-c[v]); if(d > 0 || (d == 0 && ans[v] > x)) ans[v] = x; } void dfs(int v){ set<int>::iterator it = t.lower_bound(c[v]); if(it != t.end()) up(v,*it); if(it != t.begin()) up(v,*(--it)); rep(i,ch[v].size()) dfs(ch[v][i]); t.insert(c[v]); } int main(){ int a, b; scanf("%d",&n); rep(i,n) scanf("%d",&c[i]); rep(i,n-1){ scanf("%d%d",&a,&b); ch[a].pb(b); flag[b] = true; } rep(i,n) if(!flag[i]) root = i; rep(i,n) ans[i] = INF; dfs(root); rep(i,n) reverse(rng(ch[i])); t.clear(); dfs(root); rep(i,n) printf("%d\n",ans[i]==INF?-1:ans[i]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | I - 支配と友好 |
User | snuke |
Language | C++ (G++ 4.6.4) |
Score | 200 |
Code Size | 1072 Byte |
Status | AC |
Exec Time | 374 ms |
Memory | 18260 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:36:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ./Main.cpp:37:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ./Main.cpp:39:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 200 / 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, 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 | 151 ms | 5796 KB |
binary01 | AC | 217 ms | 6440 KB |
binary02 | AC | 347 ms | 10924 KB |
binary03 | AC | 326 ms | 11184 KB |
hand00 | AC | 237 ms | 15648 KB |
line00 | AC | 166 ms | 13600 KB |
line01 | AC | 200 ms | 14112 KB |
line02 | AC | 318 ms | 18260 KB |
random00 | AC | 141 ms | 5796 KB |
random01 | AC | 158 ms | 5928 KB |
random02 | AC | 177 ms | 6056 KB |
random03 | AC | 207 ms | 6568 KB |
random04 | AC | 291 ms | 9116 KB |
random05 | AC | 328 ms | 10660 KB |
random06 | AC | 338 ms | 11052 KB |
random07 | AC | 340 ms | 11172 KB |
random08 | AC | 342 ms | 11176 KB |
sample01 | AC | 24 ms | 3100 KB |
sample02 | AC | 24 ms | 3112 KB |
sample03 | AC | 24 ms | 3228 KB |
star00 | AC | 118 ms | 4692 KB |
star01 | AC | 176 ms | 5336 KB |
star02 | AC | 272 ms | 10016 KB |
ternary00 | AC | 143 ms | 5284 KB |
ternary01 | AC | 202 ms | 5928 KB |
ternary02 | AC | 302 ms | 10396 KB |
ternary03 | AC | 330 ms | 10660 KB |
thin00 | AC | 166 ms | 8988 KB |
thin01 | AC | 158 ms | 7412 KB |
thin02 | AC | 233 ms | 9636 KB |
thin03 | AC | 221 ms | 7968 KB |
thin04 | AC | 371 ms | 14112 KB |
thin05 | AC | 352 ms | 12456 KB |
thin06 | AC | 374 ms | 14364 KB |
thin07 | AC | 333 ms | 12724 KB |
uniform00 | AC | 323 ms | 10404 KB |
uniform01 | AC | 321 ms | 10668 KB |
uniform02 | AC | 297 ms | 10408 KB |
uniform03 | AC | 322 ms | 10404 KB |
uniform04 | AC | 291 ms | 10148 KB |
uniform05 | AC | 318 ms | 10156 KB |
uniform06 | AC | 308 ms | 10016 KB |