제출 #144769

#제출 시각아이디문제언어결과실행 시간메모리
144769abekerSplit the Attractions (IOI19_split)C++17
100 / 100
420 ms72868 KiB
#include <bits/stdc++.h> using namespace std; typedef pair <int, int> pii; struct tree { int n; vector <int> weight, dad; vector <vector <pii>> adj; tree() { n = 0; } int add_node() { weight.push_back(0); dad.push_back(-1); adj.push_back({}); return n++; } void add_edge(int x, int y) { adj[x].push_back({y, 0}); adj[y].push_back({x, 0}); } void set_weight(int x, int w) { weight[x] = w; } void calc(int x, int p) { dad[x] = p; for (auto &it : adj[x]) if (it.first != p) { calc(it.first, x); weight[x] += weight[it.first]; it.second = weight[it.first]; } } int centroid() { for (int i = 0; i < n; i++) { int mx = 0; for (auto &it : adj[i]) { if (it.first == dad[i]) it.second = weight[0] - weight[i]; mx = max(mx, it.second); } if (mx <= weight[0] / 2) return i; } assert(false); } void go(int x, int p, vector <int> &v) { v.push_back(x); for (auto it : adj[x]) if (it.first != p) go(it.first, x, v); } }; struct graph { int n, timer; vector <vector <int>> adj; vector <int> disc, low; vector <int> dad, link; vector <vector <int>> comps; vector <vector <int>> memo, group; vector <int> preorder; stack <int> stk; vector <bool> art; vector <int> idx; graph(int _n) { n = _n; timer = 0; disc.resize(n); low.resize(n); dad.resize(n); link.resize(n); art.resize(n); idx.resize(n); adj.resize(n); memo.resize(2 * n); group.resize(n); for (int i = 0; i < n; i++) group[i] = {i}; } graph(){} void add_edge(int x, int y) { adj[x].push_back(y); adj[y].push_back(x); } void dfs(int x, int p) { preorder.push_back(x); disc[x] = low[x] = ++timer; link[x] = x; dad[x] = p; stk.push(x); for (auto it : adj[x]) if (!disc[it]) { dfs(it, x); if (low[it] < low[x]) { low[x] = low[it]; link[x] = link[it]; } if (low[it] >= disc[x]) { art[x] = disc[x] > 1 || disc[it] > 2; comps.push_back({x}); for (; comps.back().back() != it; stk.pop()) comps.back().push_back(stk.top()); } } else if (it != p && disc[it] < low[x]) { low[x] = disc[it]; link[x] = it; } } tree block_cut() { tree res; for (int i = 0; i < n; i++) if (art[i]) { idx[i] = res.add_node(); res.set_weight(idx[i], 1); memo[idx[i]] = {i}; } for (auto comp : comps) { int node = res.add_node(); int sz = comp.size(); memo[node] = comp; for (auto it : comp) if (art[it]) { res.add_edge(node, idx[it]); sz--; } res.set_weight(node, sz); } return res; } vector <int> st_numbering() { vector <int> prv(n, -1), nxt(n, -1), sgn(n, -1); int s = preorder[0]; int t = preorder[1]; sgn[s] = 0; nxt[s] = t; prv[t] = s; for (auto it : preorder) { if (disc[it] <= 2) continue; if (sgn[link[it]]) { sgn[dad[it]] = 0; if (nxt[dad[it]] != -1) prv[nxt[dad[it]]] = it; nxt[it] = nxt[dad[it]]; prv[it] = dad[it]; nxt[dad[it]] = it; } else { sgn[dad[it]] = 1; if (prv[dad[it]] != -1) nxt[prv[dad[it]]] = it; prv[it] = prv[dad[it]]; nxt[it] = dad[it]; prv[dad[it]] = it; } } vector <int> res; for (int x = s; x != -1; x = nxt[x]) res.push_back(x); return res; } graph induced(const vector <int> &subset) { vector <int> label(n, -1); int sz = subset.size(); for (int i = 0; i < sz; i++) label[subset[i]] = i; graph res(sz); for (int i = 0; i < sz; i++) for (auto it : adj[subset[i]]) if (label[it] != -1 && i < label[it]) res.add_edge(i, label[it]); return res; } vector <int> clip(int num) { dfs(0, -1); preorder.resize(num); return preorder; } vector <int> construct(const vector <int> &subset, const vector <pii> &p) { vector <bool> in(n, false); for (auto it : subset) in[it] = true; vector <int> rest; for (int i = 0; i < n; i++) if (!in[i]) rest.push_back(i); vector <int> A = induced(subset).clip(p[0].first); vector <int> B = induced(rest).clip(p[1].first); vector <int> res(n, p[2].second); for (auto it : A) res[subset[it]] = p[0].second; for (auto it : B) res[rest[it]] = p[1].second; return res; } }; graph G, H; tree T; vector <int> find_split(int N, int a, int b, int c, vector <int> u, vector <int> v) { vector <pii> parts = {{a, 1}, {b, 2}, {c, 3}}; sort(parts.begin(), parts.end()); G = graph(N); for (int i = 0; i < u.size(); i++) G.add_edge(u[i], v[i]); G.dfs(0, -1); T = G.block_cut(); T.calc(0, -1); int node = T.centroid(); bool single = G.memo[node].size() == 1; for (auto it : T.adj[node]) { vector <int> branch; T.go(it.first, node, branch); vector <int> tmp; for (auto it1 : branch) for (auto it2 : G.memo[it1]) if (!single || it2 != G.memo[node][0]) tmp.push_back(it2); sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin()); assert(tmp.size() == it.second); G.group[G.memo[it.first][0]] = tmp; if (it.second >= parts[0].first) return G.construct(tmp, parts); } if (single) return vector <int> (N, 0); H = G.induced(G.memo[node]); H.dfs(0, -1); vector <int> order = H.st_numbering(); vector <int> lft; for (auto it : order) { int tmp = G.memo[node][it]; for (auto it1 : G.group[tmp]) lft.push_back(it1); if (lft.size() >= parts[0].first) return G.construct(lft, parts); } assert(false); }

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:235:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); i++)
                  ~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from split.cpp:1:
split.cpp:255:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(tmp.size() == it.second);
          ~~~~~~~~~~~^~~~~~~
split.cpp:272:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (lft.size() >= parts[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...