제출 #436395

#제출 시각아이디문제언어결과실행 시간메모리
436395CodePlatina열쇠 (IOI21_keys)C++17
20 / 100
1221 ms315016 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; int n, N; const int INF = (int)1e9 + 7; vector<int> R, C; vector<vector<int>> gph[303030]; vector<int> edge[303030]; vector<bool> key[303030]; vector<pii> ran; int ord[303030]; int rev[303030]; int cnt = 0; int val = 0; bool dfs(int x) { int ret = ord[x] = ++cnt; rev[cnt] = x; edge[x].resize(N, INF); key[x].resize(N, false); vector<int> Q; Q.push_back(R[x]); while(Q.size()) { int c = Q.back(); Q.pop_back(); if(key[x][c]) continue; key[x][c] = true; for(int y : gph[x][c]) { 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]) Q.push_back(i); } } 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]); } 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(); 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; }
#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...