제출 #1058558

#제출 시각아이디문제언어결과실행 시간메모리
1058558vjudge1열쇠 (IOI21_keys)C++17
9 / 100
3070 ms31156 KiB
#include <vector> #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; int search(int n, int s, vi &r, vector<vector<ii>> &L) { vi viz(n, 0); set<int> ToVisit, Chei; ToVisit.insert(s); vector<vi> Locked(n); /// daca as avea cheia i, le-as putea vizita Chei.insert(r[s]); viz[s] = 1; while(!ToVisit.empty()) { auto u = *ToVisit.begin(); ToVisit.erase(u); for(auto [it, cul] : L[u]) { if(viz[it]) continue; if(Chei.count(cul)) { viz[it] = 1; ToVisit.insert(it); int c2 = r[it]; if(!Chei.count(c2)) { Chei.insert(c2); for(auto it2 : Locked[c2]) { if(!viz[it2]) ToVisit.insert(it2); } Locked[c2].clear(); } } else { Locked[cul].push_back(it); } } } int re = 0; for(auto it : viz) re += it; return re; } vi find_reachable(vi r, vi u, vi v, vi c) { int n = r.size(), m = u.size(); vector<vector<ii>> L(n); for(int i = 0; i < m; ++i) { L[u[i]].push_back({v[i], c[i]}); L[v[i]].push_back({u[i], c[i]}); } vi ans(n, 0), re(n, 0); for(int i = 0; i < n; ++i) ans[i] = search(n, i, r, L); int mi = ans[0]; for(auto it : ans) mi = min(mi, it); for(int i = 0; i < n; ++i) re[i] = (ans[i] == mi); return re; }
#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...