제출 #436508

#제출 시각아이디문제언어결과실행 시간메모리
436508CodePlatina열쇠 (IOI21_keys)C++17
67 / 100
1769 ms1048580 KiB
#include <vector> #include <algorithm> #include <tuple> #define pii pair<int, int> #define tiii tuple<int, int, int> #define ff first #define ss second using namespace std; //namespace A{ int n, N; const int INF = (int)1e9 + 7; vector<int> R, C; vector<vector<int>> gph[303030]; vector<int> edge[303030]; vector<vector<int>> ver[303030]; vector<bool> key[303030]; vector<pii> ran; int ord[303030]; int rev[303030]; int cnt = 0; int val = 0; void init(void) { R.clear(); C.clear(); for(int i = 0; i < n; ++i) gph[i].clear(), edge[i].clear(), key[i].clear(); ran.clear(); for(int i = 0; i < n; ++i) ord[i] = 0, rev[i + 1] = 0; cnt = val = 0; } bool dfs(int x) { int ret = ord[x] = ++cnt; rev[cnt] = x; edge[x].resize(N, INF); key[x].resize(N, false); ver[x].resize(N); vector<pii> Q; key[x][R[x]] = true; for(int y : gph[x][R[x]]) Q.push_back({y, R[x]}); while(Q.size()) { auto [y, c] = Q.back(); Q.pop_back(); if(!ord[y]) { if(dfs(y)) return true; for(int i = 0; i < N; ++i) { edge[x][i] = min(edge[x][i], edge[y][i]); if(!key[x][i] && key[y][i]) { key[x][i] = true; for(int z : gph[x][i]) Q.push_back({z, i}); for(int z : ver[x][i]) Q.push_back({z, i}); } if(key[x][i]) for(int z : ver[y][i]) Q.push_back({z, i}); else { if(ver[x][i].size() < ver[y][i].size()) swap(ver[x][i], ver[y][i]); for(int z : ver[y][i]) ver[x][i].push_back(z); } } } else edge[x][c] = min(edge[x][c], ord[y]); } for(int i = 0; i < N; ++i) { if(key[x][i]) ret = min(ret, edge[x][i]); else for(int y : gph[x][i]) { if(ord[y]) edge[x][i] = min(edge[x][i], ord[y]); else ver[x][i].push_back(y); } } if(ret < val) { val = ord[x] + 1; return true; } if(ret >= ord[x]) { ran.push_back({ord[x], cnt}); val = cnt + 1; return true; } return false; } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { n = r.size(); int m = u.size(); // init(); N = 0; for(int i = 0; i < n; ++i) N = max(N, r[i]); for(int i = 0; i < m; ++i) N = max(N, c[i]); ++N; for(int i = 0; i < n; ++i) gph[i].resize(N); R = r, C = c; for(int i = 0; i < m; ++i) { gph[u[i]][c[i]].push_back(v[i]); gph[v[i]][c[i]].push_back(u[i]); } for(int i = 0; i < n; ++i) if(!ord[i]) dfs(i); int mn = INF; for(auto [x, y] : ran) mn = min(mn, y - x); vector<int> ans(n); for(auto [x, y] : ran) if(mn == y - x) { for(int i = x; i <= y; ++i) ans[rev[i]] = 1; } return ans; } //} // //namespace B{ // // vector<pii> gph[303030]; // // void init(int n) // { // for(int i = 0; i < n; ++i) gph[i].clear(); // } // // vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) // { // int n = r.size(); // int m = u.size(); // init(n); // for(int i = 0; i < m; ++i) // { // gph[u[i]].push_back({v[i], c[i]}); // gph[v[i]].push_back({u[i], c[i]}); // } // // int cnt[n]{}; // int mn = n; // for(int x = 0; x < n; ++x) // { // bool vst[n]{}; // bool col[n]{}; // vector<int> Q; // vector<int> ls[n]; // Q.push_back(x); // while(Q.size()) // { // int i = Q.back(); Q.pop_back(); // if(vst[i]) continue; // vst[i] = true; // if(!col[r[i]]) // { // for(auto j : ls[r[i]]) Q.push_back(j); // col[r[i]] = true; // } // for(auto [j, e] : gph[i]) // { // if(col[e]) Q.push_back(j); // else ls[e].push_back(j); // } // } // for(int i = 0; i < n; ++i) if(vst[i]) ++cnt[x]; // mn = min(mn, cnt[x]); // } // // vector<int> ans(n); // for(int i = 0; i < n; ++i) if(cnt[i] == mn) ans[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...