제출 #939915

#제출 시각아이디문제언어결과실행 시간메모리
939915beaboss열쇠 (IOI21_keys)C++17
37 / 100
3077 ms36548 KiB
// Source: https://oj.uz/problem/view/IOI21_candies // #include "keys.h" #include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<pii> vpii; typedef vector<int> vi; #define FOR(i, a, b) for (int i = (a); i<b; i++) bool ckmin(int& a, int b){ return b < a ? a = b, true : false; } bool ckmax(int& a, int b){ return b > a ? a = b, true : false; } const int N = 3e5 + 10; vpii adj[N]; bool fin[N], vis[N], have[N]; vi vislist, block[N]; vi e; int here[N], res[N]; int mn = N; void reset(){ for (auto val: vislist) { have[here[val]]=false; vis[val]=false; } for (auto val: e) block[val].clear(); vislist.clear(); e.clear(); } int bfs(int _) { queue<int> q; q.push(_); vis[_]=true; vislist.pb(_); int sz = 0; while (!q.empty()) { sz++; int cur = q.front(); q.pop(); // cout << cur << ' ' << here[cur] << endl; int key = here[cur]; for (auto val: block[key]) { if (!vis[val]) { if (fin[val]) return N; // vislist.pb(val); vis[val]=true; q.push(val); // sz++; } } block[key].clear(); have[key]=true; // cout << ' ' << key << endl; for (auto val: adj[cur]) { // cout << ' ' << cur << val.f << val.s << key << endl; if (vis[val.f]) continue; if (have[val.s]) { if (fin[val.f]) return N; // vislist.pb(val.f); vis[val.f]=true; q.push(val.f); // sz++; } else { block[val.s].pb(val.f); e.pb(val.s); } } } // if (sz >= mn) sz=N; for (auto val: vislist) res[val] = min(res[val], sz); // cout << sz << endl; return sz; } vi find_reachable(vi c, vi l, vi r, vi v) { int n = c.size(); FOR(i, 0, n) { here[i] = c[i]; res[i] = N; } int m = l.size(); FOR(i, 0, m) { adj[l[i]].pb({r[i], v[i]}); adj[r[i]].pb({l[i], v[i]}); } FOR(i, 0, n) { if (!fin[i]) { int h = bfs(i); res[i] = min(res[i], h); // cout << i << h << endl; // fin[i]=true; // cout << i << h << endl; mn = min(mn, res[i]); reset(); } } vi ans(n, 0); FOR(i, 0, n) { if (res[i] == mn) { ans[i]=1; } } return ans; } // int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // vi h = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2}); // for (auto val: h) cout << val << endl; // }
#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...