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
AC × 42
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