제출 #590405

#제출 시각아이디문제언어결과실행 시간메모리
590405oleh1421열쇠 (IOI21_keys)C++17
20 / 100
3078 ms65936 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int N=500100; vector<pair<int,int> >g[N]; vector<int>go[N]; vector<int>go1[N]; int ind[N]; int cnt[N]; bool used[N]; vector<int>order; void dfs1(int v){ used[v]=true; for (int to:go1[v]){ if (!used[to]){ dfs1(to); } } order.push_back(v); } void dfs(int v){ used[v]=true; for (int to:go[v]){ if (!used[to]){ dfs(to); } } order.push_back(v); } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { int n=r.size(); int m=u.size(); for (int i=0;i<m;i++){ g[u[i]].push_back({c[i],v[i]}); g[v[i]].push_back({c[i],u[i]}); } for (int i=0;i<n;i++){ sort(g[i].begin(),g[i].end()); } vector<pair<int,int> >ans; vector<vector<int> >comp; for (int i=0;i<n;i++){ comp.push_back({i}); ind[i]=i; } int Cnt=n; while (!comp.empty()){ // if ((int)comp.size()>Cnt) exit(1); Cnt--; for (auto u:comp){ set<int>st; for (int v:u) st.insert(r[v]); int cnt=0; for (int v:u){ for (auto [c,to]:g[v]){ if (st.find(c)==st.end()) continue; if (ind[v]==ind[to] || ind[to]==-1) continue; go[ind[v]].push_back(ind[to]); go1[ind[to]].push_back(ind[v]); } } if (go[ind[u[0]]].empty()){ for (int v:u){ ans.push_back({u.size(),v}); } } } bool ok=false; for (int i=0;i<n;i++){ if (ind[i]==i && !used[i]){ if (go[i].empty()){ ok=true; dfs1(i); } } } vector<int>V; for (int i=0;i<n;i++){ if (ind[i]!=i) continue; if (!used[i]){ V.push_back(i); } } for (int i=0;i<n;i++){ if (ind[i]==-1) continue; if (used[ind[i]]) ind[i]=-1; } order.clear(); for (int i:V){ if (!used[i]) dfs(i); } reverse(order.begin(),order.end()); V=order; order.clear(); for (int i:V) used[i]=false; comp.clear(); for (int i:V){ // cout<<"X "<<i<<endl; if (!used[i]){ dfs1(i); for (int j:order) ind[j]=i; if (order.size()>1) ok=true; order.clear(); } } if (!ok) exit(1); for (int i=0;i<n;i++){ go[i].clear(); go1[i].clear(); cnt[i]=0; used[i]=false; } for (int i=0;i<n;i++){ if (ind[i]==-1) continue; go[ind[i]].push_back(i); } for (int i=0;i<n;i++){ if (!go[i].empty()) comp.push_back(go[i]); go[i].clear(); } } sort(ans.begin(),ans.end()); while (!ans.empty() && ans[0].first<ans.back().first) ans.pop_back(); vector<int>bt(n,0); for (auto cur:ans) bt[cur.second]=1; return bt; }

컴파일 시 표준 에러 (stderr) 메시지

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:55:17: warning: unused variable 'cnt' [-Wunused-variable]
   55 |             int cnt=0;
      |                 ^~~
#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...