Submission #802815

#TimeUsernameProblemLanguageResultExecution timeMemory
802815TheSahibKeys (IOI21_keys)C++17
67 / 100
3051 ms51216 KiB
#include <vector> #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int oo = 1e9 + 9; const int MAX = 3e5 + 5; struct edge{ int v, u, c; }; int n, m; vector<edge> g[MAX]; int K[MAX]; vector<int> ans; vector<bool> done(MAX, 0); int mnAns = oo; bool visited[MAX], hasKey[MAX]; vector<int> blockedList[MAX]; vector<int> keys, v, blocked; void clear(){ for(int a:v){ visited[a] = 0; } for(int a:keys){ hasKey[a] = 0; } for(auto a:blocked){ vector<int> tmp; swap(blockedList[a], tmp); } blocked.clear(); v.clear(); keys.clear(); vector<int> tmp1, tmp2, tmp3; swap(tmp1, blocked); swap(tmp2, keys); swap(tmp3, v); } queue<int> q; int cnt = 1; void add(int a){ cnt++; q.push(a); visited[a] = 1; v.push_back(a); } int bfs(int start){ queue<int> tmp; swap(tmp, q); cnt = 0; add(start); while(q.size()){ int node = q.front(); int k = K[node]; q.pop(); if(!hasKey[k]){ hasKey[k] = 1; keys.push_back(k); for(int a:blockedList[k]){ if(visited[a]) continue; if(done[a]) return oo; add(a); } } for(auto e:g[node]){ if(visited[e.u]) continue; if(hasKey[e.c]){ if(done[e.u]) return oo; add(e.u); } else{ blocked.push_back(e.c); blockedList[e.c].push_back(e.u); } } } for(int a:v){ ans[a] = min(ans[a], cnt); } return cnt; } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { n = r.size(); m = u.size(); for (int i = 0; i < n; i++) { K[i] = r[i]; } for (int i = 0; i < m; i++) { g[u[i]].push_back({u[i], v[i], c[i]}); g[v[i]].push_back({v[i], u[i], c[i]}); } ans.resize(n, oo); vector<int> order(n); iota(order.begin(), order.end(), 0); srand(time(0)); random_shuffle(order.begin(), order.end()); srand(0); random_shuffle(order.begin(), order.end()); for(int node:order){ mnAns = min(mnAns, bfs(node)); done[node] = 1; clear(); } vector<int> cnt(n, 0); for (int i = 0; i < n; i++) { if(ans[i] == mnAns){ cnt[i] = 1; } } return cnt; }
#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...