Submission #333500

#TimeUsernameProblemLanguageResultExecution timeMemory
333500leinad2족보 (KOI18_family)C++17
0 / 100
10 ms14444 KiB
#include<bits/stdc++.h> using namespace std; int k, par[300010], i, j, a, s[300010]; vector<pair<int, int> >v; struct tree { int n, leaf[300010], sz[300010]; vector<int>adj[300010]; void dfs(int v) { if(v&&v<=k) { sz[v]=1; leaf[v]=v; return; } for(int x=0;x<adj[v].size();x++) { dfs(adj[v][x]); leaf[v]=leaf[adj[v][x]]; sz[v]+=sz[adj[v][x]]; } } }t1, t2; int Find(int x) { if(x==par[x])return x; return par[x]=Find(par[x]); } void Union(int a, int b) { a=Find(a); b=Find(b); if(a!=b) { s[a]+=s[b]; s[b]=0; par[b]=a; } } int main() { scanf("%d %d %d", &t1.n, &t2.n, &k); for(i=0;i++<k;)par[i]=i,s[i]=1; for(i=0;i++<t1.n;) { scanf("%d", &a); t1.adj[a].push_back(i); } for(i=0;i++<t2.n;) { scanf("%d", &a); t2.adj[a].push_back(i); } t1.dfs(0); t2.dfs(0); for(i=0;i++<t1.n;) { if(t1.sz[i]>1)v.push_back({t1.sz[i], i}); } for(i=0;i++<t2.n;) { if(t2.sz[i]>1)v.push_back({t2.sz[i], i+t1.n}); } sort(v.begin(), v.end()); for(pair<int, int>i:v) { if(i.second>t1.n) { i.second-=t1.n; a=t2.leaf[i.second]; for(int j:t2.adj[i.second]) { Union(t2.leaf[j], a); } } else { a=t1.leaf[i.second]; for(int j:t1.adj[i.second]) { Union(t1.leaf[j], a); } } if(s[Find(a)]!=i.first) { puts("NO"); return 0; } } puts("YES"); }

Compilation message (stderr)

family.cpp: In member function 'void tree::dfs(int)':
family.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(int x=0;x<adj[v].size();x++)
      |                     ~^~~~~~~~~~~~~~
family.cpp: In function 'int main()':
family.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%d %d %d", &t1.n, &t2.n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
family.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...