Submission #1178117

#TimeUsernameProblemLanguageResultExecution timeMemory
1178117AlgorithmWarriorMergers (JOI19_mergers)C++20
100 / 100
633 ms75232 KiB
#include <bits/stdc++.h> using namespace std; int const INF=1000000000; int const MAX=500005; int color[MAX]; int n,k; vector<int>tree[MAX]; int lcol[MAX],rcol[MAX]; int l[MAX],r[MAX]; int frunze; struct answer{ int fii,st,dr; }; void read(){ cin>>n>>k; int i; for(i=1;i<n;++i){ int u,v; cin>>u>>v; tree[u].push_back(v); tree[v].push_back(u); } for(i=1;i<=n;++i) cin>>color[i]; } void minself(int& x,int val){ if(x>val) x=val; } void maxself(int& x,int val){ if(x<val) x=val; } void euler(int nod,int tata){ static int time=0; l[nod]=++time; for(auto fiu : tree[nod]) if(fiu!=tata) euler(fiu,nod); r[nod]=++time; minself(lcol[color[nod]],l[nod]); maxself(rcol[color[nod]],r[nod]); } void init(){ int i; for(i=1;i<=k;++i){ lcol[i]=INF; rcol[i]=-INF; } } answer dfs(int nod,int tata){ int nrf=0; int st=INF,dr=-INF; for(auto fiu : tree[nod]) if(fiu!=tata){ answer ans=dfs(fiu,nod); nrf+=ans.fii; minself(st,ans.st); maxself(dr,ans.dr); } minself(st,lcol[color[nod]]); maxself(dr,rcol[color[nod]]); if(st==l[nod] && dr==r[nod]){ if((nrf==0 && nod!=1) || (nrf==1 && nod==1)) ++frunze; return {1,INF,-INF}; } return {nrf,st,dr}; } int main() { read(); init(); euler(1,0); dfs(1,0); cout<<(frunze+1)/2; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...