Submission #64974

#TimeUsernameProblemLanguageResultExecution timeMemory
64974gs18115족보 (KOI18_family)C++14
0 / 100
18 ms16760 KiB
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int INF=1e9; const int MAXN=3e5+10; vector<int>adj[2][MAXN]; bool vi[MAXN]; int K,i,j; int root[2],N[2]; int pa[2][MAXN],leaf[2][MAXN]; int lev[MAXN],sz[MAXN],par[MAXN];//unionfind int chk[MAXN]; int cnt; int parent(int x) { if(par[x]==-1) return x; return par[x]=parent(par[x]); } void Union(int x,int y) { int X=parent(x); int Y=parent(y); if(X==Y) return; if(lev[X]>lev[Y]) { par[Y]=X; sz[X]+=sz[Y]; } else if(lev[Y]>lev[X]) { par[X]=Y; sz[Y]+=sz[X]; } else if(sz[X]>sz[Y]) { par[Y]=X; sz[X]+=sz[Y]; } else { par[X]=Y; sz[Y]+=sz[X]; } } struct NODE { int sz,lv; int tree,node; }tree[2][MAXN]; vector<NODE>sorting; bool cmp(NODE a,NODE b) { return a.sz!=b.sz?a.sz<b.sz:a.lv>b.lv; } void pc(int t,int h) { adj[t][pa[t][h]].push_back(h); if(vi[h]) return; vi[h]=true; if(pa[t][h]!=-1) pc(t,pa[t][h]); return; } pair<int,int>dfs(int t,int h,int lv) { tree[t][h].lv=lv; tree[t][h].tree=t; tree[t][h].node=h; if(adj[t][h].empty()) { leaf[t][h]=h; tree[t][h].sz=1; return make_pair(h,1); } pair<int,int>P; P=dfs(t,adj[t][h][0],lv+1); leaf[t][h]=P.first; int s=P.second; for(int i=1;i<adj[t][h].size();i++) { P=dfs(t,adj[t][h][i],lv+1); s+=P.second; } tree[t][h].sz=s; return make_pair(leaf[t][h],tree[t][h].sz); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>N[0]>>N[1]>>K; for(i=0;i<N[0];i++) { cin>>pa[0][i]; if(pa[0][i]==0) root[0]=i; pa[0][i]--; } for(i=0;i<N[1];i++) { cin>>pa[1][i]; if(pa[1][i]==0) root[1]=i; pa[1][i]--; } fill(vi,vi+N[0],false); for(i=0;i<K;i++) pc(0,i); fill(vi,vi+N[1],false); for(i=0;i<K;i++) pc(1,i); dfs(0,root[0],0); dfs(1,root[1],0); for(i=0;i<2;i++) for(j=K;j<N[i];j++) sorting.push_back(tree[i][j]); sort(sorting.begin(),sorting.end(),cmp); fill(par,par+MAXN,-1); fill(sz,sz+MAXN,1); for(i=0;i<sorting.size();i++) { NODE X=sorting[i]; for(j=0;j<adj[X.tree][X.node].size();j++) { int Y=adj[X.tree][X.node][j]; Union(leaf[X.tree][X.node],leaf[X.tree][Y]); } if(sz[parent(leaf[X.tree][X.node])]!=X.sz) return cout<<"NO",0; } cout<<"YES"; return 0; }

Compilation message (stderr)

family.cpp: In function 'std::pair<int, int> dfs(int, int, int)':
family.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<adj[t][h].size();i++)
                 ~^~~~~~~~~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:125:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<sorting.size();i++)
             ~^~~~~~~~~~~~~~~
family.cpp:128:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<adj[X.tree][X.node].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...