제출 #655473

#제출 시각아이디문제언어결과실행 시간메모리
655473dooompySplit the Attractions (IOI19_split)C++17
0 / 100
573 ms1048576 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; int n, m; int par[100005], sz[100005]; vector<int> graph[100005], tree[100005], inter[100005]; pair<int, int> info[3]; int findset(int i) { return (i == par[i] ? i : par[i] = findset(par[i])); } bool onion(int a, int b) { a = findset(a), b = findset(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); par[b] = a; sz[a] += sz[b]; return true; } void dfscent(int node, int par = -1) { sz[node] = 1; for (auto nxt : tree[node]) { if (nxt == par) continue; dfscent(nxt, node); sz[node] += sz[nxt]; } } int centroid(int node, int par = -1) { for (auto nxt : tree[node]) { if (nxt == par) continue; if (sz[nxt] * 2 >sz[0]) return centroid(nxt, node); } return node; } vector<int> nodes; void dfs(int node, int par) { nodes.push_back(node); for (auto nxt : graph[node]) { if (nxt == par) continue; onion(nxt, node); dfs(nxt, node); } } int state[100005]; bool createseen[100005]; vector<int> ansnodes; void dfscreate(int node) { ansnodes.push_back(node); createseen[node] = true; for (auto nxt : graph[node]) { if (!createseen[nxt] && state[nxt] == state[node]) dfscreate(nxt); } } vector<int> create() { vector<int> ans(n, info[2].second); for (auto cur : nodes) { state[cur] = 1; } for (int i = 0; i < n; i++) { if (state[i] == 1 && !createseen[i]) { ansnodes.clear(); dfscreate(i); for (int j = 0; j < info[0].first; j++) { ans[ansnodes[j]] = info[0].second; } } if (state[i] == 0 && !createseen[i]) { ansnodes.clear(); dfscreate(i); for (int j = 0; j < info[1].first; j++) { ans[ansnodes[j]] = info[1].second; } } } return ans; } bool seen[100005]; vector<int> across; void dfsacross(int node) { across.push_back(node); seen[node] = true; for (auto nxt : inter[node]) { if (!seen[nxt]) dfsacross(nxt); } } vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) { n = _n; m = p.size(); info[0] = {a, 0}; info[1] = {b, 1}; info[2] = {c, 2}; sort(info, info + 3); for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } for (int i = 0; i < m; i++) { graph[p[i]].push_back(q[i]); graph[q[i]].push_back(p[i]); if (onion(p[i], q[i])) { tree[p[i]].push_back(q[i]); tree[q[i]].push_back(p[i]); } } dfscent(0); int cent = centroid(0); for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } for (auto nxt : tree[cent]) { nodes.clear(); dfs(nxt, cent); if (nodes.size() >= info[0].first) { // rest are connected return create(); } } for (int i = 0; i < m; i++) { if (p[i] == cent || q[i] == cent) continue; int a = findset(p[i]), b = findset(q[i]); if (a == b) continue; inter[a].push_back(b); inter[b].push_back(a); } for (int i = 0; i < n; i++) { if (findset(i) == i && i != c && !seen[i]) { across.clear(); dfsacross(i); int ct = 0; set<int> used; for (auto tre : across) { ct += sz[findset(tre)]; used.insert(tre); if (ct >= info[0].first) break; } if (ct >= info[0].first) { nodes.clear(); for (int j = 0; j < n; j++) { if (used.count(findset(j))) nodes.push_back(j); } return create(); } } } return vector<int> (n, 0); }

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:149:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |         if (nodes.size() >= info[0].first) {
      |             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
#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...