Submission #403520

#TimeUsernameProblemLanguageResultExecution timeMemory
403520zaneyu족보 (KOI18_family)C++14
44 / 100
2 ms776 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=2e3+5; vector<int> v[maxn],v2[maxn]; vector<int> vv[maxn],vv2[maxn]; int k; void dfs(int u){ if(u<k) vv[u].pb(u); for(int x:v[u]){ dfs(x); for(auto z:vv[x]) vv[u].pb(z); } } void dfs2(int u){ if(u<k) vv2[u].pb(u); for(int x:v2[u]){ dfs2(x); for(auto z:vv2[x]) vv2[u].pb(z); } } bool cmp(vector<int> &a,vector<int> &b){ return sz(a)<sz(b); } 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); REP(i,n) sort(ALL(vv[i])); REP(i,m) sort(ALL(vv2[i])); sort(vv,vv+n,cmp); sort(vv2,vv2+m,cmp); int p=0; REP(i,k) par[i]=i,rank1[i]=1; REP(i,n){ while(p<m and sz(vv2[p])<=sz(vv[i])){ for(auto x:vv2[p]) merge(x,vv2[p][0]); ++p; } for(auto x:vv[i]) merge(x,vv[i][0]); if(rank1[find(vv[i][0])]!=sz(vv[i])){ 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...