제출 #1058742

#제출 시각아이디문제언어결과실행 시간메모리
1058742qwusha열쇠 (IOI21_keys)C++17
9 / 100
3014 ms34320 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second typedef long double ld; const ld eps = 1e-8; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); const ll inf = 1e18; const ll mod = 1e9 + 7; #include "keys.h" vector<set<int>> g; vector<vector<pair<int, int>>> gr; vector<int> num; int cnt = 0; void dfs(int v, int number) { num[v] = number; cnt++; for (auto u : g[v]) { if (num[u] == -1) { dfs(u, number); } } } vector<int> find_reachable(vector<int> r, vector<int> fir, vector<int>sec, vector<int> c) { bool first = 1; ll n = r.size(); int m = fir.size(); for (int i = 0; i < m; i++) { if (c[i] != 0) first = 0; } if (!first) { gr.resize(n); for (int i = 0; i < m; i++) { gr[fir[i]].push_back({sec[i], c[i]}); gr[sec[i]].push_back({fir[i], c[i]}); } vector<int> p(n); for (int i = 0; i < n; i++) { set<int> keys = {r[i]}; set<int> pos = {i}; vector<int> used(n, 0); vector<set<int>> reach(n); while (!pos.empty()) { auto v = *pos.begin(); pos.erase(pos.begin()); p[i]++; used[v] = 1; if (keys.find(r[v]) == keys.end()) { keys.insert(r[v]); for (auto nod : reach[r[v]]) { if (!used[nod]) pos.insert(nod); } } for (auto [u, w] : gr[v]) { if (!used[u]) { if (keys.find(w) != keys.end()) { pos.insert(u); } else { reach[w].insert(u); } } } } } int mini = n + 1; for (int i = 0; i < n; i++) { mini = min(mini, p[i]); } vector<int> res(n); for (int i = 0; i < n; i++) { if (p[i] == mini) res[i] = 1; cout << p[i] << ' '; } cout << endl; return res; } g.resize(n); for (int i = 0; i < m; i++) { g[fir[i]].insert(sec[i]); g[sec[i]].insert(fir[i]); } vector<int> res(n); bool nonzer = 0; for (int i = 0; i < n; i++) { if (r[i] != 0) nonzer = 1; } num.resize(n, -1); vector<int> sz; int mini = n + 1; for (int i = 0; i < n; i++) { if (num[i] == -1) { cnt = 0; dfs(i, sz.size()); sz.push_back(cnt); mini = min(mini, cnt); } } for (int i = 0; i < n; i++) { if (nonzer) { if (r[i] != 0 || sz[num[i]] == 1) { res[i] = 1; } } else { if (sz[num[i]] == mini) { res[i] = 1; } } } return res; } /* int main() { vector<int> r = {0, 1, 1, 2, 2, 1, 2}, u = {0, 0, 1, 1, 2, 3, 3, 4, 4, 5}, v = {1, 2, 2, 3, 3, 4, 5, 5, 6, 6}, c = {0, 0, 1, 0, 0, 1, 2, 0, 2, 1}; auto res = find_reachable(r,u,v,c); for (int i = 0; i < r.size(); i++) { cout << res[i] << ' '; } } */
#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...