제출 #557562

#제출 시각아이디문제언어결과실행 시간메모리
557562timreizin낙하산 고리들 (IOI12_rings)C++17
37 / 100
3129 ms121660 KiB
#include <vector> #include <numeric> #include <array> #include <algorithm> using namespace std; struct DSU { int n, comps; vector<int> parent, size; vector<int> adj; array<int, 5> counter; int res, v; DSU(int n = 0, int v = -1) : n(n), v(v) { parent.resize(n); size.resize(n, 1); iota(parent.begin(), parent.end(), 0); comps = n; adj.resize(n); counter.fill(0); counter[0] = n; res = (v == -1 ? n : 1); } int getParent(int i) { if (parent[i] == i) return i; return parent[i] = getParent(parent[i]); } void unite(int a, int b) { if (res == 0) return; if (a == v || b == v) return; int wasCyc = comps - counter[0] - counter[1] / 2; --counter[min(adj[a], 4)]; --counter[min(adj[b], 4)]; ++adj[a]; ++adj[b]; ++counter[min(adj[a], 4)]; ++counter[min(adj[b], 4)]; if (counter[3] + counter[4] > 0) { res = 0; return; } a = getParent(a); b = getParent(b); if (a != b) --comps; int newCyc = comps - counter[0] - counter[1] / 2; if (v != -1 && newCyc > 0) { res = 0; return; } else if (v == -1) { if (newCyc >= 2) { res = 0; return; } if (newCyc == 1 && wasCyc == 0) { vector<int> cnt(n); for (int i = 0; i < n; ++i) { if (adj[i] < 2) cnt[getParent(i)] = -1e9; else ++cnt[getParent(i)]; } res = 0; for (int i = 0; i < n; ++i) res = max(res, cnt[i]); } } if (a != b) { if (size[a] < size[b]) swap(a, b); size[a] += size[b]; parent[b] = a; } } }; int n; vector<vector<int>> adj; array<DSU, 8> dsu; array<int, 5> counter; vector<int> curs, dop; vector<pair<int, int>> edges; void Init(int N_) { n = N_; adj.resize(n); dsu[0] = DSU(n); counter[0] = n; curs.push_back(-1); } void Link(int a, int b) { int was3 = counter[3], was4 = counter[4]; --counter[min((int)adj[a].size(), 4)]; --counter[min((int)adj[b].size(), 4)]; adj[a].push_back(b); adj[b].push_back(a); ++counter[min((int)adj[a].size(), 4)]; ++counter[min((int)adj[b].size(), 4)]; if (counter[4] > 1) return; if (counter[4] > was4) { curs.clear(); dop.clear(); for (int i = 0; i < 7; ++i) dsu[i].res = 0; if (adj[a].size() == 4) curs.push_back(a); if (adj[b].size() == 4) curs.push_back(b); dsu[0] = DSU(n, curs[0]); for (auto [a, b] : edges) dsu[0].unite(a, b); } else if (counter[3] > was3) { if (counter[3] > 4 && was3 <= 4) { curs.clear(); dop.clear(); for (int i = 0; i < 7; ++i) dsu[i].res = 0; } if (counter[3] <= 4) { if (was3 == 0) curs.clear(); if (adj[a].size() == 3) curs.push_back(a); if (adj[b].size() == 3) curs.push_back(b); for (int i = 0; i < 7; ++i) dsu[i].res = 0; dop.clear(); for (int i = 0; i < curs.size(); ++i) { dsu[i] = DSU(n, curs[i]); for (auto [a, b]: edges) dsu[i].unite(a, b); } //calc dop if (curs.size() < 3) { for (int i = 0; i < n; ++i) { if (adj[i].size() < 3) { bool was0 = false, was1 = curs.size() == 1; for (int j: adj[i]) { was0 = was0 || (j == curs[0]); if (curs.size() == 2) was1 = was0 || (j == curs[1]); } if (was0 && was1) { dop.push_back(i); } } } } for (int i = 0; i < dop.size(); ++i) { dsu[i + curs.size()] = DSU(n, dop[i]); for (auto [a, b]: edges) dsu[i + curs.size()].unite(a, b); } } } for (int i = 0; i < curs.size(); ++i) dsu[i].unite(a, b); for (int i = 0; i < dop.size(); ++i) dsu[i + curs.size()].unite(a, b); edges.emplace_back(a, b); } int CountCritical() { if (counter[4] > 1) return 0; int res = 0; for (int i = 0; i < 8; ++i) res += dsu[i].res; return res; }

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

rings.cpp: In function 'void Link(int, int)':
rings.cpp:139:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for (int i = 0; i < curs.size(); ++i)
      |                             ~~^~~~~~~~~~~~~
rings.cpp:164:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             for (int i = 0; i < dop.size(); ++i)
      |                             ~~^~~~~~~~~~~~
rings.cpp:171:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for (int i = 0; i < curs.size(); ++i) dsu[i].unite(a, b);
      |                     ~~^~~~~~~~~~~~~
rings.cpp:172:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for (int i = 0; i < dop.size(); ++i) dsu[i + curs.size()].unite(a, b);
      |                     ~~^~~~~~~~~~~~
#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...