제출 #334571

#제출 시각아이디문제언어결과실행 시간메모리
334571IgorISplit the Attractions (IOI19_split)C++17
100 / 100
192 ms22272 KiB
const long long MOD = 998244353; const long long INF = 1e9; const long long INFLL = 1e18; #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<ll> vll; typedef complex<double> cd; #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++) #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define popcount(x) __builtin_popcount(x) #define popcountll(x) __builtin_popcountll(x) #define fi first #define se second #define re return #define pb push_back #define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin()) #ifdef LOCAL #define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl #define ln cerr << __LINE__ << endl #else #define dbg(x) void(0) #define ln void(0) #endif // LOCAL int cx[4] = {-1, 0, 1, 0}; int cy[4] = {0, -1, 0, 1}; string Yes[2] = {"No\n", "Yes\n"}; string YES[2] = {"NO\n", "YES\n"}; string Possible[2] = {"Impossible\n", "Possible\n"}; string POSSIBLE[2] = {"IMPOSSIBLE\n", "POSSIBLE\n"}; void dfs2(int v, int p, vi &vis, vvi &g, vi &col, int color, vi &sz, int cent) { vis[v] = 2; col[v] = color; for (auto u : g[v]) if (vis[u] != 2) { if ((sz[u] < sz[cent] && sz[u] < sz[cent]) || (sz[v] > sz[cent] && sz[u] > sz[cent])) dfs2(u, v, vis, g, col, color, sz, cent); } } void dfs(int v, int p, vi &vis, vi &sz, int &cent, int &centp, vvi &g, int n) { vis[v] = 1; sz[v] = 1; for (auto u : g[v]) if (vis[u] == 0) { dfs(u, v, vis, sz, cent, centp, g, n); sz[v] += sz[u]; } if (cent == -1 && sz[v] * 2 >= n) { cent = v; centp = p; } } void dfs3(int v, int color, vi &vis, vi &col, vi &ans, int A, int &x, vvi &g) { vis[v] = 1; if (x) ans[v] = A, x--; for (auto u : g[v]) { if (ans[u] == 0 && vis[u] == 0 && (color == -1 || (col[u] == color))) { dfs3(u, color, vis, col, ans, A, x, g); } } } vi find_split(int n, int a, int b, int c, vi p, vi q) { vvi g(n); for (int i = 0; i < p.size(); i++) { g[p[i]].pb(q[i]); g[q[i]].pb(p[i]); } int cent = -1, centp = -1; vi vis(n), sz(n), col(n), croot(n); dfs(0, 0, vis, sz, cent, centp, g, n); int color = 1; vis[cent] = 2; for (auto u : g[cent]) if (vis[u] != 2 && sz[u] < sz[cent]) { dfs2(u, cent, vis, g, col, color, sz, cent); croot[color] = u; color++; } if (centp != cent) { dfs2(centp, cent, vis, g, col, color, sz, cent); croot[color] = centp; } //cout << "cent = " << cent << "\n"; //for (int i = 0; i < n; i++) // cout << col[i] << " "; //cout << "\n"; vector<pii> s = {{a, 1}, {b, 2}, {c, 3}}; sort(all(s)); int A = s[0].first; vector<int> ans(n); vector<int> cnt(n); for (int i = 0; i < n; i++) cnt[col[i]]++; for (int i = 1; i < n; i++) { if (cnt[i] >= A) { //cout << i << ", " << croot[i] << "\n"; int x = s[0].first; vis = vi(n, 0); dfs3(croot[i], i, vis, col, ans, s[0].second, x, g); x = s[1].first; vis = vi(n, 0); dfs3(cent, -1, vis, col, ans, s[1].second, x, g); for (int j = 0; j < n; j++) if (ans[j] == 0) ans[j] = s[2].second; return ans; } } vector<vector<int> > groups(n); for (int i = 0; i < n; i++) { groups[col[i]].push_back(i); } for (int j = 0; j < p.size(); j++) { int f = p[j], t = q[j]; if (f != cent && t != cent && col[f] != col[t]) { int c1 = col[f]; int c2 = col[t]; if (groups[c1].size() < groups[c2].size()) { for (auto v : groups[c1]) col[v] = c2, groups[c2].push_back(v); } else { for (auto v : groups[c2]) col[v] = c1, groups[c1].push_back(v); } if (groups[c1].size() >= A) { int i = c1; int x = s[0].first; vis = vi(n, 0); dfs3(croot[i], i, vis, col, ans, s[0].second, x, g); x = s[1].first; vis = vi(n, 0); dfs3(cent, -1, vis, col, ans, s[1].second, x, g); for (int j = 0; j < n; j++) if (ans[j] == 0) ans[j] = s[2].second; return ans; } if (groups[c2].size() >= A) { int i = c2; int x = s[0].first; vis = vi(n, 0); dfs3(croot[i], i, vis, col, ans, s[0].second, x, g); x = s[1].first; vis = vi(n, 0); dfs3(cent, -1, vis, col, ans, s[1].second, x, g); for (int j = 0; j < n; j++) if (ans[j] == 0) ans[j] = s[2].second; return ans; } } } return ans; }

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

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < p.size(); i++)
      |                     ~~^~~~~~~~~~
split.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int j = 0; j < p.size(); j++)
      |                     ~~^~~~~~~~~~
split.cpp:161:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |             if (groups[c1].size() >= A)
      |                 ~~~~~~~~~~~~~~~~~~^~~~
split.cpp:174:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  174 |             if (groups[c2].size() >= A)
      |                 ~~~~~~~~~~~~~~~~~~^~~~
#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...