Submission #558935

#TimeUsernameProblemLanguageResultExecution timeMemory
558935nghiass001Keys (IOI21_keys)C++17
37 / 100
3035 ms27552 KiB
#include <bits/stdc++.h> #define FOR(i,l,r) for(int i=(l); i<=(r); ++i) #define REP(i,l,r) for(int i=(l); i<(r); ++i) #define FORD(i,r,l) for(int i=(r); i>=(l); --i) #define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i) #define pii pair<int, int> using namespace std; const int N = 1e5 + 5; int n, m, key_in[N], is_key[N], avail[N]; vector<pii> S[N]; vector<int> list_edge[N]; int solve(int u) { fill(is_key, is_key + n, 0); fill(avail, avail + n, 0); REP(i, 0, n) list_edge[i].clear(); vector<int> Q; int cnt = 1; avail[u] = 1; Q.push_back(u); while (!Q.empty()) { u = Q.back(); Q.pop_back(); if (!is_key[key_in[u]]) { is_key[key_in[u]] = 1; for(int v : list_edge[key_in[u]]) if (!avail[v]) { ++cnt; avail[v] = 1; Q.push_back(v); } } for(auto [v, type] : S[u]) if (!avail[v]) { if (is_key[type]) { ++cnt; avail[v] = 1; Q.push_back(v); } else list_edge[type].push_back(v); } } return cnt; } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { n = r.size(); m = u.size(); vector<int> ans(n, 0); REP(i, 0, n) key_in[i] = r[i]; REP(i, 0, m) { S[u[i]].emplace_back(v[i], c[i]); S[v[i]].emplace_back(u[i], c[i]); } int mini = n; REP(i, 0, n) { ans[i] = solve(i); mini = min(mini, ans[i]); } REP(i, 0, n) ans[i] = (mini == ans[i]); 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...