Submission #403624

#TimeUsernameProblemLanguageResultExecution timeMemory
403624zaneyu족보 (KOI18_family)C++14
0 / 100
9 ms14468 KiB
/*input 7 8 4 7 7 6 6 0 5 5 6 7 7 8 0 5 5 5 */ #include<bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<=n;i++) #define ll long long #define pii pair<int,int> #define pb push_back #define ALL(x) x.begin(),x.end() #define f first #define s second #define sz(x) (int)x.size() const int maxn=3e5+5; vector<int> v[maxn],v2[maxn]; int sz[maxn],sz2[maxn]; int id[maxn],id2[maxn]; int k; void dfs(int u){ if(u<k) id[u]=u,sz[u]=1; for(int x:v[u]){ dfs(x); id[u]=id[x]; sz[u]+=sz[x]; } } void dfs2(int u){ if(u<k) id2[u]=u,sz2[u]=1; for(int x:v2[u]){ dfs2(x); id2[u]=id2[x]; sz2[u]+=sz2[x]; } } int par[maxn],rank1[maxn]; int find(int u){ if(par[u]==u) return u; return par[u]=find(par[u]); } void merge(int a,int b){ a=find(a),b=find(b); if(a==b) return; par[a]=b; rank1[b]+=rank1[a]; } int main(){ ios::sync_with_stdio(false),cin.tie(0); int n,m; cin>>n>>m>>k; int r1,r2; REP(i,n){ int x; cin>>x; --x; if(x!=-1) v[x].pb(i); else r1=i; } REP(i,m){ int x; cin>>x; --x; if(x!=-1) v2[x].pb(i); else r2=i; } dfs(r1),dfs2(r2); vector<pii> va,vb; REP(i,n) if(sz[i]>1){ va.pb({sz[i],i}); } REP(i,m) if(sz2[i]>1){ vb.pb({sz2[i],i}); } sort(ALL(va)),sort(ALL(vb)); int p=0; REP(i,k) par[i]=i,rank1[i]=1; REP(i,sz(va)){ while(p<sz(vb) and vb[p].f<=va[i].f){ for(auto x:v2[vb[p].s]) merge(id2[x],id2[vb[p].s]); ++p; } for(auto x:v[va[i].s]) merge(id[x],id[va[i].s]); if(rank1[find(id[va[i].s])]!=va[i].f){ cout<<"NO\n"; return 0; } } cout<<"YES\n"; }

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:70:17: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     dfs(r1),dfs2(r2);
      |             ~~~~^~~~
family.cpp:70:8: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     dfs(r1),dfs2(r2);
      |     ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...