제출 #437710

#제출 시각아이디문제언어결과실행 시간메모리
437710jeroenodb열쇠 (IOI21_keys)C++17
67 / 100
2596 ms239916 KiB
#include "bits/stdc++.h" #include "keys.h" // #pragma GCC optimize "Ofast" // #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // #pragma GCC optimize("unroll-loops") #ifdef LOCAL #include "grader.cpp" #endif using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e5+1, oo = 1e9; std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int r){return std::uniform_int_distribution<int>(0,r-1)(rng);} struct blockedges { vvi blocked; unordered_set<int> used; blockedges(int n) { blocked.resize(n); } void add(int r, int to) { if(blocked[r].empty()) used.insert(r); blocked[r].push_back(to); } void reset() { for(int i:used) blocked[i].clear(); used.clear(); } }; vi find_reachable(vi r, vi u, vi v, vi c) { int n = r.size(); vvi adj(n); int m=u.size(); for(int i=0;i<m;++i) { adj[u[i]].push_back(i); adj[v[i]].push_back(i); } for(int i=0;i<n;++i) { random_shuffle(all(adj[i]),rnd); } vector<unordered_set<int>> sets(n); vi par(n,-1); vector<bool> done(n); int minimum=oo; blockedges bl(n); vi order; { // generate random ordering based on degree of nodes vi sharr; sharr.reserve(2*m+n); vector<bool> used(n); for(int i=0;i<m;++i) sharr.push_back(u[i]), sharr.push_back(v[i]); for(int i=0;i<n;++i) sharr.push_back(i); random_shuffle(all(sharr),rnd); for(int i:sharr) { if(!used[i]) order.push_back(i); used[i]=true; } } for(auto start : order) { bl.reset(); // Simulate process stack<int> explore; struct el { int at; vi::iterator it; }; stack<el> extend; unordered_set<int> keys; auto& vis = sets[start]; auto add = [&](int to) { if(!vis.count(to)) { if(done[to]) { if(par[to]==-2) par[start]=-2; else if(sets[par[to]].count(start)) { // stop simulating, exact same set already simulated. par[start] = par[to]; } else par[start]=-2; // this set is strictly bigger than another, no point in simulating return; } vis.insert(to); keys.insert(r[to]); explore.push(to); extend.push({to, adj[to].begin()}); } }; auto floodfill = [&]() { while(!explore.empty()) { int at = explore.top(); explore.pop(); vi& unblock = bl.blocked[r[at]]; while(!unblock.empty()) { int to = unblock.back(); unblock.pop_back(); add(to); if(par[start]!=-1 or (int)vis.size()>minimum) break; } } }; add(start); floodfill(); while(par[start]==-1 and (int)vis.size()<=minimum and !extend.empty()) { auto& cur = extend.top(); if(cur.it==adj[cur.at].end()) { extend.pop(); continue; } int eid = *cur.it; int to = u[eid]^v[eid]^cur.at; if(keys.count(c[eid])) { // already have key, explore directly add(to); floodfill(); } else if(!vis.count(to)) { // add to blocked vertices: vertices that have an edge to them, but we haven't got the key yet bl.add(c[eid],to); } cur.it++; } if(par[start]==-1) { // finished whole simulation par[start]=start; minimum = min(minimum,(int)vis.size()); } done[start]=true; } vi ans(n,0); for(int i=0;i<n;++i) { if(par[i]>=0 and (int)sets[par[i]].size()==minimum) 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...