Submission #251225

#TimeUsernameProblemLanguageResultExecution timeMemory
251225teee족보 (KOI18_family)C++14
100 / 100
368 ms64340 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; int par[300'010]; int sz[300'010]; int kk; int find(int n){ return par[n]?par[n]=find(par[n]):n; } void merge(int a,int b){ a=find(a); b=find(b); if(a^b){ sz[a]+=sz[b]; par[b]=a; } } vector<int> v[2][300'010]; vector<pair<int,vector<int>>> check; pair<int,int> dfs(int n,int idx){ if(n&&n<=kk){ sz[n]=1; return {1,n}; } int cnt=0; vector<int> t; int c=0; for(auto i:v[idx][n]){ pair<int,int> k=dfs(i,idx); if(k.first>0) { cnt += k.first; t.push_back(k.second); c = k.second; } } if(cnt>1&&t.size()>1)check.emplace_back(cnt,t); return {cnt,c}; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n1,n2,a; cin>>n1>>n2>>kk; for(int i=1;i<=n1;i++){ cin>>a; v[0][a].push_back(i); } for(int i=1;i<=n2;i++){ cin>>a; v[1][a].push_back(i); } dfs(0,0); dfs(0,1); sort(check.begin(),check.end()); for(const auto& i:check){ vector<int> t=i.second; int cnt=i.first; int p=find(t[0]); for(auto j:t){ merge(p,j); } if(sz[find(p)]!=cnt){ cout<<"NO";return 0; } } cout<<"YES"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...