Submission #139115
Source Code Expand
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<complex>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define sz(x) (int)(x).size()
#define popcount __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
const int MX = 100005, INF = 1000000000;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-10;
const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; //<^>v
int n;
int a[MX];
int c[MX], mj[MX];
vi to[MX];
int ans[MX];
void cdfs(int v){
c[v] = 1;
rep(i,to[v].size()){
int u = to[v][i];
cdfs(u);
c[v] += c[u];
}
}
void mdfs(int v){
mj[v] = n;
rep(i,to[v].size()){
int u = to[v][i];
mdfs(u);
if(c[mj[v]] < c[u]) mj[v] = u;
}
}
map<int,int> t;
void adfs(int v){
t[a[v]]++;
rep(i,sz(to[v])){
int u = to[v][i];
adfs(u);
}
}
void ddfs(int v){
map<int,int>::iterator it = t.lower_bound(a[v]);
if((*it).se == 1){
t.erase(it);
} else (*it).se--;
rep(i,sz(to[v])){
int u = to[v][i];
ddfs(u);
}
}
void dfs(int v){
ans[v] = -1;
map<int,int>::iterator it = t.lower_bound(a[v]);
if(it != t.end()) ans[v] = (*it).fi;
if(it != t.begin()){
--it;
if(ans[v] == -1 || (ans[v]-a[v])>=(a[v]-(*it).fi)) ans[v] = (*it).fi;
}
rep(i,sz(to[v])){
int u = to[v][i];
if(u == mj[v]) continue;
adfs(u);
}
if(mj[v] != n){
dfs(mj[v]);
}
rep(i,sz(to[v])){
int u = to[v][i];
if(u == mj[v]) continue;
ddfs(u);
dfs(u);
adfs(u);
}
t[a[v]]++;
}
int main(){
int aa, bb;
scanf("%d",&n);
rep(i,n) scanf("%d",&a[i]);
rep(i,n-1){
scanf("%d%d",&aa,&bb);
to[aa].pb(bb);
c[bb]++;
}
int root = 0;
rep(i,n) if(!c[i]) root = i;
cdfs(root);
mdfs(root);
dfs(root);
rep(i,n) printf("%d\n",ans[i]);
return 0;
}
Submission Info
Submission Time
2014-03-02 17:46:31+0900
Task
I - 支配と友好
User
snuke
Language
C++ (G++ 4.6.4)
Score
200
Code Size
2548 Byte
Status
AC
Exec Time
1191 ms
Memory
18976 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:117:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:118:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:120:24: 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
346 ms
6432 KB
binary01
AC
638 ms
7188 KB
binary02
AC
1191 ms
11688 KB
binary03
AC
1106 ms
11884 KB
hand00
AC
268 ms
16420 KB
line00
AC
177 ms
14372 KB
line01
AC
200 ms
14752 KB
line02
AC
271 ms
18976 KB
random00
AC
208 ms
6492 KB
random01
AC
262 ms
6564 KB
random02
AC
303 ms
6752 KB
random03
AC
390 ms
7204 KB
random04
AC
655 ms
9820 KB
random05
AC
763 ms
11436 KB
random06
AC
756 ms
11684 KB
random07
AC
740 ms
11804 KB
random08
AC
779 ms
11936 KB
sample01
AC
24 ms
3232 KB
sample02
AC
24 ms
3116 KB
sample03
AC
24 ms
3112 KB
star00
AC
123 ms
5404 KB
star01
AC
171 ms
5912 KB
star02
AC
297 ms
10660 KB
ternary00
AC
270 ms
6048 KB
ternary01
AC
511 ms
6624 KB
ternary02
AC
944 ms
11168 KB
ternary03
AC
950 ms
11300 KB
thin00
AC
170 ms
9640 KB
thin01
AC
170 ms
8032 KB
thin02
AC
247 ms
10284 KB
thin03
AC
212 ms
8744 KB
thin04
AC
334 ms
14812 KB
thin05
AC
296 ms
13220 KB
thin06
AC
303 ms
15012 KB
thin07
AC
302 ms
13476 KB
uniform00
AC
921 ms
11052 KB
uniform01
AC
1005 ms
11424 KB
uniform02
AC
782 ms
11152 KB
uniform03
AC
732 ms
11044 KB
uniform04
AC
514 ms
10780 KB
uniform05
AC
566 ms
10784 KB
uniform06
AC
467 ms
10716 KB