Submission #1203400

#TimeUsernameProblemLanguageResultExecution timeMemory
1203400simona1230열쇠 (IOI21_keys)C++20
9 / 100
449 ms36728 KiB
#include <bits/stdc++.h> #include "keys.h" using namespace std; const int maxn=2*1e5+5; vector<pair<int,int> > v[maxn]; void ae(int i,int j,int z) { v[i].push_back({j,z}); v[j].push_back({i,z}); } int cnt,used[maxn]; int in[maxn]; int k[maxn]; int bg; bool f; vector<int> e[maxn], u; int l[maxn],done[maxn]; int fl(int x) { if(l[x]==x)return x; return l[x]=fl(l[x]); } void unite(int i,int j) { i=fl(i); j=fl(j); l[j]=i; } void dfs(int i) { if(f)return; if(fl(i)!=bg) { //cout<<i<<" ! "<<bg<<endl; f=1; done[i]=1; unite(i,bg); return; } //cout<<i<<endl; cnt++; in[k[i]]=1; used[i]=1; u.push_back(i); for(int j=0; j<e[k[i]].size(); j++) { int nb=e[k[i]][j]; if(used[nb])continue; dfs(nb); } e[k[i]].clear(); for(int j=0; j<v[i].size(); j++) { pair<int,int> nb=v[i][j]; if(used[nb.first])continue; if(in[nb.second])dfs(nb.first); else { u.push_back(nb.second); e[nb.second].push_back(nb.first); } } } vector<int> p; void dfs1(int i) { if(fl(i)==bg)p.push_back(i); //cout<<i<<endl; cnt++; in[k[i]]=1; used[i]=1; u.push_back(i); for(int j=0; j<e[k[i]].size(); j++) { int nb=e[k[i]][j]; if(used[nb])continue; dfs(nb); } e[k[i]].clear(); for(int j=0; j<v[i].size(); j++) { pair<int,int> nb=v[i][j]; if(used[nb.first])continue; if(in[nb.second])dfs1(nb.first); else { u.push_back(nb.second); e[nb.second].push_back(nb.first); } } } std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) { for(int i=0; i<R.size(); i++) k[i]=R[i],l[i]=i; for(int i=0; i<U.size(); i++) ae(U[i],V[i],C[i]); for(int j=0; j<=20; j++) { memset(done,0,sizeof(done)); for(int i=0; i<R.size(); i++) { if(done[i]||fl(i)!=i)continue; //cout<<i<<"!"<<endl; bg=i; dfs(i); for(int x=0;x<u.size();x++) { in[k[u[x]]]=used[u[x]]=0; e[u[x]].clear(); } u.clear(); f=0; } } vector<int> ans; int minn=R.size(); for(int i=0;i<R.size();i++) { if(fl(i)==i) { bg=i; cnt=0; dfs1(i); if(cnt<minn) { minn=cnt; ans=p; } else if(cnt==minn) { for(int j=0;j<p.size();j++) ans.push_back(p[j]); } for(int x=0;x<u.size();x++) { in[k[u[x]]]=used[u[x]]=0; e[u[x]].clear(); } u.clear(); p.clear(); } } vector<int> h=ans; ans.clear(); for(int i=0;i<R.size();i++) ans.push_back(0); for(int i=0;i<h.size();i++) ans[h[i]]=1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...