제출 #435843

#제출 시각아이디문제언어결과실행 시간메모리
435843Noam527열쇠 (IOI21_keys)C++17
9 / 100
836 ms125504 KiB
#include <bits/stdc++.h> typedef long long ll; typedef long double ldb; const int md = 1e9 + 7; const ll inf = 3e18; const int OO = 0; using namespace std; const int N = 3e5 + 5; struct group { int root; int state; // 0,1,2 int cursed; // 0,1 set<pair<int, int>> e; set<int> k; vector<int> q; group() {} int work() { while (q.size()) { int ke = q.back(); auto it = e.lower_bound(make_pair(ke, -1)); if (it != e.end() && it->first == ke) { int res = it->second; e.erase(it); return res; } q.pop_back(); } return -1; } }; int par[N]; group groups[N]; int root(int x) { if (x == par[x]) return x; return par[x] = root(par[x]); } void merge(group &G, group &H) { par[H.root] = G.root; if (G.q.size() < H.q.size()) { swap(G.q, H.q); } if (G.e.size() < H.e.size()) { swap(G.e, H.e); } if (G.k.size() < H.k.size()) { swap(G.k, H.k); } G.cursed = max(G.cursed, H.cursed); for (const auto &i : H.q) G.q.push_back(i); H.q.clear(); for (const auto &i : H.e) { if (G.k.count(i.first) || H.k.count(i.first)) { G.q.push_back(i.first); } G.e.insert(i); } H.e.clear(); for (const auto &i : H.k) { auto it = G.e.lower_bound(make_pair(i, -1)); auto it2 = H.e.lower_bound(make_pair(i, -1)); if ((it != G.e.end() && it->first == i) || (it2 != H.e.end() && it2->first == i)) { G.q.push_back(i); } G.k.insert(i); } H.k.clear(); } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { int n = r.size(), m = u.size(); for (int i = 0; i <= n; i++) par[i] = i; for (int i = 0; i < n; i++) { groups[i].root = i; groups[i].state = 0; groups[i].cursed = 0; groups[i].k.insert(r[i]); groups[i].q.push_back(r[i]); } for (int i = 0; i < m; i++) { groups[u[i]].e.insert(make_pair(c[i], v[i])); groups[v[i]].e.insert(make_pair(c[i], u[i])); } groups[n].root = n; groups[n].state = 1; groups[n].cursed = 1; groups[n].k.insert(0); groups[n].q.push_back(0); for (int i = 0; i < n; i++) groups[n].e.insert(groups[n].e.end(), make_pair(0, i)); vector<int> stack = { n }; while (stack.size()) { if (OO) { cout << "stack: "; for (const auto &i : stack) cout << i << " "; cout << '\n'; } int r = stack.back(); int v = groups[r].work(); if (OO) { cout << "r, v: " << r << " " << v << '\n'; } if (v == -1) { groups[r].state = 2; stack.pop_back(); if (stack.size()) groups[stack.back()].cursed = 1; continue; } v = root(v); if (OO) { cout << "root of v: " << v << '\n'; } if (groups[v].state == 2) { if (OO) cout << "visited already :(\n"; groups[r].cursed = 1; continue; } if (groups[v].state == 0) { if (OO) cout << "new!\n"; groups[v].state = 1; stack.push_back(v); continue; } // cycle :) if (v == r) { if (OO) cout << "dumb cycle :(\n"; // stupid cycle :( continue; } if (OO) cout << "good cycle\n"; while (groups[stack.back()].root != v) { stack.pop_back(); merge(groups[stack.back()], groups[r]); } if (OO) cout << '\n'; } vector<vector<int>> clusters(n); for (int i = 0; i < n; i++) { int r = root(i); if (groups[r].cursed == 0) clusters[r].push_back(i); } int mnsize = md; for (int i = 0; i < n; i++) if (clusters[i].size()) mnsize = min(mnsize, (int)clusters[i].size()); vector<int> result(n, 0); for (int i = 0; i < n; i++) { if (clusters[i].size() == mnsize) { for (const auto &j : clusters[i]) result[j] = 1; } } return result; } /* void solve() { int n, m; cin >> n >> m; vector<int> r(n), u(m), v(m), c(m); for (auto &i : r) cin >> i; for (auto &i : u) cin >> i; for (auto &i : v) cin >> i; for (auto &i : c) cin >> i; for (const auto &i : find_reachable(r, u, v, c)) cout << i << " "; cout << '\n'; } int main() { //ios::sync_with_stdio(0), cin.tie(0); int tst = 1; //cin >> tst; while (tst--) solve(); } */

컴파일 시 표준 에러 (stderr) 메시지

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:105:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  105 |    for (const auto &i : stack) cout << i << " "; cout << '\n';
      |    ^~~
keys.cpp:105:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |    for (const auto &i : stack) cout << i << " "; cout << '\n';
      |                                                  ^~~~
keys.cpp:159:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  159 |   if (clusters[i].size() == mnsize) {
      |       ~~~~~~~~~~~~~~~~~~~^~~~~~~~~
#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...