제출 #264743

#제출 시각아이디문제언어결과실행 시간메모리
264743kdh9949Split the Attractions (IOI19_split)C++17
100 / 100
221 ms24696 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using vint = vector<int>; using vll = vector<ll>; using vld = vector<ld>; using vpii = vector<pii>; using vpil = vector<pil>; using vpli = vector<pli>; using vpll = vector<pll>; #define x first #define y second #define all(v) v.begin(),v.end() vint solve(int n, int a, int b, vector<vint> &e) { vector<vint> te(n); vint pn(n), low(n), mlow(n), sz(n), par(n); function<void(int, int)> g = [&](int x, int y) { static int pc = 0; mlow[x] = pn[x] = ++pc; sz[x] = 1; par[x] = y; low[x] = x; for(int i : e[x]) { if(i == y) continue; if(!pn[i]) { te[x].push_back(i); te[i].push_back(x); g(i, x); sz[x] += sz[i]; mlow[x] = min(mlow[x], mlow[i]); } else { if(pn[low[x]] > pn[i]) low[x] = i; } } mlow[x] = min(mlow[x], pn[low[x]]); }; g(0, -1); function<int(int, int)> f = [&](int x, int y) { for(int i : te[x]) if(i != y && sz[i] >= a) return f(i, x); return x; }; int X = f(0, -1); for(int &c : te[X]) { if(mlow[c] < pn[X] && sz[X] - sz[c] >= a) { sz[X] -= sz[c]; function<int(int, int, int)> rr = [&](int x, int y, int r) { if(pn[low[x]] < r) { te[x].push_back(low[x]); te[low[x]].push_back(x); return 1; } for(int i : te[x]) if(i != y && rr(i, x, r)) return 1; return 0; }; rr(c, X, pn[X]); for(int &y : te[c]) if(y == X) y = -1; c = -1; } } if(n - sz[X] >= a) { vint ans(n, 3); int cnt; function<void(int, int, int)> h = [&](int x, int y, int c) { if(cnt) { cnt--; ans[x] = c; } for(int i : te[x]) if(i >= 0 && i != y) h(i, x, c); }; int dir = (sz[X] <= n / 2); cnt = (dir ? a : b); h(X, par[X], 1 + !dir); cnt = (dir ? b : a); h(par[X], X, 1 + dir); return ans; } else return vint(n, 0); } vint find_split(int n, int a, int b, int c, vint p, vint q) { vint v = {0, a, b, c}; vint col = {0, 1, 2, 3}; sort(all(col), [&](int x, int y){ return v[x] < v[y]; }); vector<vint> e(n); for(int i = 0; i < p.size(); i++) { e[p[i]].push_back(q[i]); e[q[i]].push_back(p[i]); } vint ans = solve(n, v[col[1]], v[col[2]], e); for(int &x : ans) x = col[x]; return ans; }

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

split.cpp: In function 'vint find_split(int, int, int, int, vint, vint)':
split.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  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...