제출 #334105

#제출 시각아이디문제언어결과실행 시간메모리
334105IgorISplit the Attractions (IOI19_split)C++17
0 / 100
711 ms1048576 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, vvi &g, vi &col, vi &croot, int n) { vis[v] = 1; sz[v] = 1; for (auto u : g[v]) if (vis[u] == 0) { dfs(u, v, vis, sz, cent, g, col, croot, n); sz[v] += sz[u]; } if (cent == -1 && sz[v] * 2 >= n) { cent = v; int color = 1; vis[cent] = 2; for (auto u : g[v]) if (vis[u] != 2 && sz[u] < sz[v]) { dfs2(u, v, vis, g, col, color, sz, cent); croot[color] = u; color++; } if (p != v) { dfs2(p, v, vis, g, col, color, sz, cent); croot[color] = p; } } } void dfs3(int v, int color, vi &col, vi &ans, int A, int &x, vvi &g) { if (x) ans[v] = A, x--; for (auto u : g[v]) { if (ans[u] == 0 && (color == -1 || (col[u] == color))) { dfs3(u, color, 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; vi vis(n), sz(n), col(n), croot(n); dfs(0, 0, vis, sz, cent, g, col, croot, n); //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 = 0; i < n; i++) { if (cnt[i] >= A) { int x = s[0].first; dfs3(croot[i], i, col, ans, s[0].second, x, g); x = s[1].first; dfs3(cent, -1, 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:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     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...