Submission #489526

#TimeUsernameProblemLanguageResultExecution timeMemory
489526kiomiUnique Cities (JOI19_ho_t5)C++17
100 / 100
458 ms56432 KiB
//#pragma GCC target ("avx2") //#pragma GCC optimization ("Ofast") //#pragma GCC optimization ("unroll-loops") //#pragma comment(linker,"/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //order_of_key(k): Number of items strictly smaller than k . //find_by_order(k): K-th element in a set (counting from zero). #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define full(x,n) x,x+n+1 #define full(x) x.begin(),x.end() #define finish return 0 #define putb push_back #define f first #define s second //logx(a^n)=loga(a^n)/logx(a) //logx(a*b)=logx(a)+logx(b) //logx(y)=log(y)/log(x) //logb(n)=loga(n)/loga(b) #define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> #define putf push_front #define gainb pop_back //(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n //(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i #define gainf pop_front #define len(x) (int)x.size() // 1/b%mod=b^(m-2)%mod // (a>>x)&1==0 // a^b=(a+b)-2(a&b) typedef double db; typedef long long ll; //sum of squares n*(n+1)*(2n+1)/6 //sum of cubes [n*(n+1)/2]^2 //sum of squares for odds n*(4*n*n-1)/3 //sum of cubes for odds n*n*(2*n*n-1) const int ary=1e6+5; const ll mod=1e9+7; const ll inf=1e18; using namespace std; using namespace __gnu_pbds; int n,m,c[ary],d[ary],mx1[ary],mx2[ary],ans[ary],res,cnt[ary]; vector<int> g[ary],q; void dfs(int v,int pr=0){ d[v]=d[pr]+1; mx1[v]=mx2[v]=v; for(int i=0;i<len(g[v]);i++){ int to=g[v][i]; if(to==pr){ continue; } dfs(to,v); if(d[mx2[v]]<d[mx1[to]]){ mx2[v]=mx1[to]; } if(d[mx1[v]]<d[mx2[v]]){ swap(mx1[v],mx2[v]); } } } void del(){ res-=--cnt[c[q.back()]]==0; q.pop_back(); } void add(int v){ q.push_back(v); res+=cnt[c[v]]++==0; } void go(int v,int pr=0){ for(int i=0;i<len(g[v]);i++){ int to=g[v][i]; if(to==pr||mx1[to]!=mx1[v]){ continue; } while(len(q)&&d[mx2[v]]-d[v]>=d[v]-d[q.back()]){ del(); } add(v); go(to,v); } for(int i=0;i<len(g[v]);i++){ int to=g[v][i]; if(to==pr||mx1[to]==mx1[v]){ continue; } while(len(q)&&d[mx1[v]]-d[v]>=d[v]-d[q.back()]){ del(); } add(v); go(to,v); } while(len(q)&&d[mx1[v]]-d[v]>=d[v]-d[q.back()]){ del(); } ans[v]=max(ans[v],res); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } for(int i=1;i<=n;i++){ cin>>c[i]; } dfs(1); int A=mx1[1]; d[A]=0; dfs(A); go(A); while(len(q)){ del(); } int B=mx1[A]; d[B]=0; dfs(B); go(B); for(int i=1;i<=n;i++){ cout<<ans[i]<<"\n"; } }

Compilation message (stderr)

joi2019_ho_t5.cpp:15: warning: "full" redefined
   15 | #define full(x) x.begin(),x.end()
      | 
joi2019_ho_t5.cpp:14: note: this is the location of the previous definition
   14 | #define full(x,n) x,x+n+1
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...