Submission #146262

#TimeUsernameProblemLanguageResultExecution timeMemory
146262jwvg0425Split the Attractions (IOI19_split)C++17
40 / 100
221 ms22960 KiB
#include "split.h" #include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; vector<int> edge[100005]; vector<int> treeEdge[100005]; bool visited[100005]; int cent; int val[100005]; int csize[100005]; int treeNum[100005]; int parent[100005]; int treeSize[100005]; int compSize[100005]; bool usingTree[100005]; int usingSize; void dfs(int root) { visited[root] = true; for (auto& e : edge[root]) { if (visited[e]) continue; treeEdge[root].push_back(e); treeEdge[e].push_back(root); dfs(e); } } int findCent(int root, int n) { csize[root] = 1; bool isCent = true; for (auto& e : treeEdge[root]) { if (e == parent[root]) continue; parent[e] = root; int c = findCent(e, n); if (c != -1) return c; csize[root] += csize[e]; isCent = isCent && (csize[e] <= (n + 1) / 2); } if (isCent && n - csize[root] <= (n + 1) / 2) return root; return -1; } int treeDfs(int root, int k) { // cent 방향 안 가면서 크기 계산, 트리 번호도 붙여준다 int res = 1; visited[root] = true; treeNum[root] = k; for (auto& e : treeEdge[root]) { if (treeNum[e] != 0 || e == cent) continue; res += treeDfs(e, k); } return res; } int comp(int root) { int res = 0; if (!usingTree[treeNum[root]]) { res += treeSize[treeNum[root]]; usingTree[treeNum[root]] = true; } visited[root] = true; for (auto& e : edge[root]) { if (visited[e] || e == cent) continue; res += comp(e); } return res; } void findTree(int root, int sz) { if (usingSize >= sz) return; if (!usingTree[treeNum[root]]) { usingSize += treeSize[treeNum[root]]; usingTree[treeNum[root]] = true; } for (auto& e : edge[root]) { if (visited[e] || e == cent) continue; findTree(e, sz); } } void mark(int root, int v, int& sz) { if (sz == 0) return; val[root] = v; sz--; for (auto& e : edge[root]) { if (val[e] != 0 || !usingTree[treeNum[e]]) continue; mark(e, v, sz); } } void mark2(int root, int v, int& sz) { if (sz == 0) return; val[root] = v; sz--; for (auto& e : edge[root]) { if (val[e] != 0) continue; mark2(e, v, sz); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { vector<ii> v = { { a, 1 }, { b, 2 }, { c, 3 } }; for (int i = 0; i < p.size(); i++) { edge[p[i]].push_back(q[i]); edge[q[i]].push_back(p[i]); } dfs(0); sort(all(v)); cent = findCent(0, n); // centroid 제외한 그래프에서 a이상의 크기인 트리가 있는지 확인, 있으면 go int tr = 1; for (auto& e : edge[cent]) { treeSize[tr] = treeDfs(e, tr); tr++; } memset(visited, false, sizeof(visited)); for (auto& e : edge[cent]) { int c = comp(e); if (c < v[0].xx) continue; // 합해서 a이상 되는 트리 확인 후, 그 트리에 속하는 원소들만 이용해서 a개수 만든다 memset(visited, false, sizeof(visited)); memset(usingTree, false, sizeof(usingTree)); findTree(e, v[0].xx); mark(e, v[0].yy, v[0].xx); mark2(cent, v[1].yy, v[1].xx); for (int i = 0; i < n; i++) if (val[i] == 0) val[i] = v[2].yy; break; } vector<int> result(n); for (int i = 0; i < n; i++) result[i] = val[i]; return result; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:182:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.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...