Submission #130524

#TimeUsernameProblemLanguageResultExecution timeMemory
130524Bodo171Mergers (JOI19_mergers)C++14
100 / 100
2195 ms190164 KiB
#include <iostream> #include <fstream> #include <map> #include <vector> using namespace std; const int nmax=500005; map<int,int> ap[nmax]; vector<int> v[nmax]; int l[nmax],r[nmax],p[nmax],closed[nmax],w[nmax],sons[nmax],rele[nmax],tot[nmax],col[nmax],c[nmax],tt[nmax]; int nr,n,i,paths,k,x,y,frz; void baga(int path,int cc) { ap[path][cc]++; if(ap[path][cc]==1) rele[path]++; if(ap[path][cc]==tot[cc]) rele[path]--; } void dfs(int x) { int big=0; w[x]=1; ++nr;l[x]=nr;col[nr]=c[x]; for(int i=0;i<v[x].size();i++) if(!w[v[x][i]]) { tt[v[x][i]]=x; dfs(v[x][i]); if(w[v[x][i]]>w[big]) big=v[x][i]; w[x]+=w[v[x][i]]; } if(big&&(!closed[big])) p[x]=p[big]; else { p[x]=++paths; if(big) sons[paths]++; } baga(p[x],c[x]); for(int i=0;i<v[x].size();i++) if(v[x][i]!=big&&v[x][i]!=tt[x]) { if(closed[v[x][i]]) sons[p[x]]++; else { sons[p[x]]+=sons[p[v[x][i]]]; for(int j=l[v[x][i]];j<=r[v[x][i]];j++) baga(p[x],col[j]); } } if(rele[p[x]]==0) { closed[x]=1; if(sons[p[x]]==0) frz++; } r[x]=nr; } int main() { //freopen("data.in","r",stdin); ios_base::sync_with_stdio(false); cin>>n>>k; for(i=1;i<=n-1;i++) { cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } for(i=1;i<=n;i++) { cin>>c[i]; tot[c[i]]++; } dfs(1); if(sons[p[1]]==1) frz++; if(frz==1) frz=0; cout<<(frz+1)/2; return 0; }

Compilation message (stderr)

mergers.cpp: In function 'void dfs(int)':
mergers.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
mergers.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
#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...