제출 #441808

#제출 시각아이디문제언어결과실행 시간메모리
441808alan8585열쇠 (IOI21_keys)C++17
9 / 100
96 ms17220 KiB
#include <vector> #include <stack> #include <set> #include <map> #include <bitset> #include <queue> using namespace std; const int MAXN = 3000; int T, in[MAXN], low[MAXN], instack[MAXN], bs[MAXN]; vector<pair<int, int>> e[MAXN]; vector<pair<int, int>> re[MAXN]; stack<int> st; vector<vector<int>> SCC; vector<int> flags; void dfs(int a) { instack[a] = 1; st.push(a); in[a] = low[a] = ++T; for(pair<int, int> i : e[a]) { if(!in[i.first]) { dfs(i.first); low[a] = min(low[a], low[i.first]); } else if(instack[i.first]) { low[a] = min(low[a], in[i.first]); } } if(in[a] == low[a]) { int now = -1; SCC.push_back(vector<int>(0)); do { now = st.top(); bs[now] = (int)SCC.size() - 1; st.pop(); instack[now] = 0; SCC.back().push_back(now); } while(now != a); } } set<int> has_key; map<int, set<int>> key_can_open; bitset<MAXN> vis; queue<int> q; int solve(int a, vector<int> &r) { int ans = 0; q.push(a); vis.reset(); vis[a] = 1; key_can_open.clear(); has_key.clear(); for(pair<int, int> i : re[a]) { key_can_open[i.second].insert(i.first); } while(!q.empty()) { int now = q.front(); q.pop(); ans += (int)SCC[now].size(); for(int i : SCC[now]) { if(now != a) SCC[a].push_back(i); if(has_key.find(r[i]) == has_key.end()) { has_key.insert(r[i]); for(int j : key_can_open[r[i]]) { if(!vis[j]) { vis[j] = 1; q.push(j); for(pair<int, int> i : re[j]) { key_can_open[i.second].insert(i.first); } } } } } } return ans; } std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { std::vector<int> ans(r.size(), 0); int n = r.size(), m = u.size(); for(int i = 0; i < m; i++) { if(r[u[i]] == c[i]) e[u[i]].push_back(make_pair(v[i], c[i])); if(r[v[i]] == c[i]) e[v[i]].push_back(make_pair(u[i], c[i])); } for(int i = 0; i < n; i++) { if(!in[i]) { dfs(i); } } int nmin = MAXN; vector<int> ansv; for(int i = 0; i < (int)SCC.size(); i++) for(int j : SCC[i]) for(pair<int, int> k : e[j]) if(bs[k.first] != i) re[bs[k.first]].push_back(make_pair(i, k.second)); for(int i = 0; i < (int)SCC.size(); i++) { int flag = 1; for(int j : SCC[i]) { for(pair<int, int> k : e[j]) { if(bs[k.first] != i) { flag = 0; } } } flags.push_back(flag); if(flag) { int now = solve(i, r); if(nmin > now) { nmin = now; } } } for(int i = 0; i < (int)SCC.size(); i++) { if(flags[i] && (int)SCC[i].size() == nmin) { for(int j : SCC[i]) ans[j] = 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...