Submission #1043720

#TimeUsernameProblemLanguageResultExecution timeMemory
104372042kangarooKeys (IOI21_keys)C++17
0 / 100
1 ms344 KiB
#include "keys.h" #include "bits/stdc++.h" using namespace std; using g_t = vector<map<int, vector<int>>>; using g_t2 = vector<vector<int>>; int find(int a, vector<int> &p) { if (p[a] == a) return a; return p[a] = find(p[a], p); } bool unite(int a, int b, vector<int> &p, g_t &g, vector<int> &si, vector<set<int>> &in) { a = find(a, p), b = find(b, p); if (a == b) return false; if (si[a] < si[b]) swap(a, b); p[b] = a; si[a] += si[b]; in[a].insert(in[b].begin(), in[b].end()); for (auto [co, e]: g[b]) { for (auto ed: e) { if (find(ed, p) != a) g[a][co].push_back(ed); } } return true; } void poO(int n, int &t, g_t &g, g_t2 &rev, vector<set<int>> &whi, vector<int> &poOv, vector<int> &p) { n = find(n, p); if (poOv[n] == -2) return; poOv[n] = -2; for (auto e: whi[n]) { if (g[n].find(e) != g[n].end()) { for (auto f: g[n][e]) { f = find(f, p); rev[f].push_back(n); poO(f, t, g, rev, whi, poOv, p); } } } poOv[n] = t++; } void markDfs(int n, int co, g_t2 &g, vector<int> col, vector<int> &p) { n = find(n, p); if (col[n] != -1) return; col[n] = co; for (auto e: g[n]) { e = find(e, p); markDfs(e, co, g, col, p); } } std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { int n = r.size(); g_t in(r.size()); for (int i = 0; i < u.size(); ++i) { in[u[i]][c[i]].push_back(v[i]); in[v[i]][c[i]].push_back(u[i]); } vector<int> p(n), si(n, 1); iota(p.begin(), p.end(), 0); vector<set<int>> whi(n); for (int i = 0; i < n; ++i) { whi[i].insert(r[i]); } bool ch = true; while (ch) { ch = false; int t = 0; vector<int> pos(n, -1); g_t2 gT(n); for (int i = 0; i < n; ++i) { poO(i, t, in, gT, whi, pos, p); } vector<int> o(n); std::iota(o.begin(), o.end(), 0); std::sort(o.begin(), o.end(), [&](int l, int r) { return pos[l] > pos[r]; }); vector<int> col(n, -1); for (int i = 0; i < n; ++i) { if (pos[o[i]] != -1) { markDfs(o[i], o[i], gT, col, p); } } for (int i = 0; i < n; ++i) { if (col[i] != -1) ch = unite(col[i], i, p, in, si, whi) || ch; } } vector<int> re(n, 1); for (int i = 0; i < n; ++i) { if (i == find(i, p)) { for (auto e: whi[i]) { if (in[i].find(e) != in[i].end()) { for (auto f: in[i][e]) { f = find(f, p); re[i] = re[i] && f == i; } } } } } int mi = n; for (int i = 0; i < n; ++i) { if (re[find(i, p)]) { mi = min(mi, si[find(i, p)]); } } for (int i = 0; i < n; ++i) { re[i] = re[find(i, p)] && mi == si[find(i, p)]; } return re; }

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < u.size(); ++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...