제출 #832906

#제출 시각아이디문제언어결과실행 시간메모리
832906amunduzbaev열쇠 (IOI21_keys)C++17
39 / 100
1303 ms76160 KiB
#include "bits/stdc++.h" using namespace std; #define ar array typedef long long ll; //~ #define int ll vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { int n = r.size(); int m = u.size(); vector<vector<ar<int, 2>>> edges(n); for(int i=0;i<m;i++){ edges[u[i]].push_back({v[i], c[i]}); edges[v[i]].push_back({u[i], c[i]}); } int res = n + 1; vector<int> mask(n); vector<int> ans; if(n <= 2000 && m <= 2000 && false){ vector<int> used(n), cviz(n); vector<vector<int>> q; int cnt = 0; for(int i=0;i<n;i++){ fill(used.begin(), used.end(), 0); fill(cviz.begin(), cviz.end(), 0); q.assign(n, vector<int>()); cnt = 0; queue<int> qq; qq.push(i); while(!qq.empty()){ cnt++; int u = qq.front(); qq.pop(); used[u] = 1; if(!cviz[r[u]]){ cviz[r[u]] = 1; for(auto x : q[r[u]]){ if(!used[x]){ used[x] = 1; qq.push(x); } } } for(auto [x, c] : edges[u]){ if(used[x]) continue; if(cviz[c]){ used[x] = 1; qq.push(x); } else { //~ assert(false); q[c].push_back(x); } } } if(res > cnt) res = cnt, ans.clear(); if(res == cnt) ans.push_back(i); } fill(used.begin(), used.end(), 0); for(auto x : ans) used[x] = 1; return used; } for(int i=0;i<n;i++){ mask[i] |= (1 << r[i]); } vector<int> tin(n), fup(n), cmp(n), ss; for(int T=0;T<30;T++){ int t = 0; fill(cmp.begin(), cmp.end(), 0); fill(tin.begin(), tin.end(), 0); fill(fup.begin(), fup.end(), 0); ss.clear(); function<void(int)> dfs = [&](int u){ tin[u] = fup[u] = ++t; ss.push_back(u); for(auto [x, c] : edges[u]){ if(!(mask[u] >> c & 1)) continue; if(!tin[x]) { dfs(x); fup[u] = min(fup[u], fup[x]); } else if(!cmp[x]){ fup[u] = min(fup[u], tin[x]); } } if(tin[u] == fup[u]){ vector<int> tmp; int x, tot = 0; do{ x = ss.back(); ss.pop_back(); tmp.push_back(x); tot |= mask[x]; }while(x != u); for(auto x : tmp){ //~ cout<<x<<" "; cmp[x] = 1; mask[x] = tot; } //~ cout<<"\n"; } }; for(int i=0;i<n;i++){ if(cmp[i]) continue; dfs(i); } //~ cout<<"\n"; } //~ for(int i=0;i<n;i++){ //~ for(int j=0;j<n;j++) cout<<(mask[i] >> j & 1); //~ cout<<"\n"; //~ } int t = 0, last = 0; ss.clear(); fill(cmp.begin(), cmp.end(), 0); fill(tin.begin(), tin.end(), 0); fill(fup.begin(), fup.end(), 0); function<void(int)> dfs = [&](int u){ tin[u] = fup[u] = ++t; ss.push_back(u); for(auto [x, c] : edges[u]){ if(!(mask[u] >> c & 1)) continue; if(!tin[x]) { dfs(x); fup[u] = min(fup[u], fup[x]); } else if(!cmp[x]){ fup[u] = min(fup[u], tin[x]); } } if(tin[u] == fup[u]){ last++; int x; do{ x = ss.back(); ss.pop_back(); cmp[x] = last; //~ cout<<x<<" "; }while(x != u); //~ cout<<"\n"; } }; vector<vector<int>> g(n + 1); for(int i=0;i<n;i++){ if(cmp[i]) continue; dfs(i); } vector<int> sz(n + 1); for(int i=0;i<n;i++){ sz[cmp[i]]++; for(auto [x, c] : edges[i]){ if((mask[i] >> c & 1) && cmp[i] != cmp[x]){ g[cmp[i]].push_back(cmp[x]); } } } vector<int> viz(n + 1), used(n); for(int i=1;i<=last;i++){ if(g[i].empty()){ if(res > sz[i]) res = sz[i], ans.clear(); if(res == sz[i]) ans.push_back(i); } } for(auto x : ans){ viz[x] = 1; } for(int i=0;i<n;i++){ if(viz[cmp[i]]) used[i] = 1; } return used; }
#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...