제출 #295815

#제출 시각아이디문제언어결과실행 시간메모리
295815ChrisTSplit the Attractions (IOI19_split)C++17
100 / 100
215 ms21144 KiB
#include <bits/stdc++.h> #include "split.h" using namespace std; const int MN = 1e5+5; vector<int> adj[MN]; int sz[MN], ohp[MN], p[MN], togo[MN]; bool vis[MN]; int dfs (int cur) { vis[cur] = 1; for (int i : adj[cur]) if (!vis[i]) { ohp[i] = cur; sz[cur] += dfs(i); } return ++sz[cur]; } int getcent (int cur, int tot) { for (int i : adj[cur]) if (ohp[i] == cur && sz[i] > (tot >> 1)) return getcent(i,tot); return cur; } int calc (int cur) { vis[cur] = sz[cur] = 1; for (int i : adj[cur]) if ((ohp[i] == cur || ohp[cur] == i) && !vis[i]) { p[i] = cur; sz[cur] += calc(i); } return sz[cur]; } vector<int> find_split (int n, int a, int b, int c, vector<int> P, vector<int> Q) { vector<pair<int,int>> vv = {{a,1},{b,2},{c,3}}; sort(vv.begin(),vv.end()); vector<int> ret(n,vv[2].second); a = vv[0].first; b = vv[1].first; c = vv[2].first; for (int i = 0; i < (int)P.size(); i++) { adj[++P[i]].push_back(++Q[i]); adj[Q[i]].push_back(P[i]); } auto fillB = [&] (int st, int go, int put) { queue<int> q; q.push(st); ret[st-1] = put; --go; while (!q.empty()) { int cur = q.front(); q.pop(); for (int i : adj[cur]) if (ret[i-1] == vv[2].second) { q.push(i); if (go) --go, ret[i-1] = put; else return; } } }; int cent = getcent(1,dfs(1)); memset(vis,0,sizeof vis); calc(cent); for (int i : adj[cent]) if (p[i] == cent && sz[i] >= a) { queue<int> q; q.push(i); while (a--) { int cur = q.front(); q.pop(); ret[cur-1] = vv[0].second; for (int j : adj[cur]) if (p[j] == cur) q.push(j); } fillB(cent,b,vv[1].second); return ret; } vector<vector<int>> ree; vector<int> cnt,in(n+1); for (int i : adj[cent]) if (p[i] == cent) { in[i] = (int)ree.size(); ree.push_back({i}); cnt.push_back(sz[i]); queue<int> q; q.push(i); while (!q.empty()) { int cur = q.front(); q.pop(); togo[cur] = i; for (int j : adj[cur]) if (p[j] == cur) q.push(j); } } for (int i = 0; i < (int)P.size(); i++) if (p[P[i]] != Q[i] && p[Q[i]] != P[i] && in[P[i]] != in[Q[i]]) { int u = in[togo[P[i]]], v = in[togo[Q[i]]]; if (u == v) continue; if (cnt[u] > cnt[v]) swap(u,v); cnt[v] += cnt[u]; for (int j : ree[u]) {in[j] = v; ree[v].push_back(j);} } for (int i = 0; i < (int)ree.size(); i++) if (cnt[i] >= a) { while (cnt[i] - sz[ree[i].back()] >= a) { ree[i].pop_back(); cnt[i] -= sz[ree[i].back()]; } for (int j : ree[i]) { queue<int> q; q.push(j); while (a && !q.empty()) { int cur = q.front(); q.pop(); --a; ret[cur-1] = vv[0].second; for (int k : adj[cur]) if (p[k] == cur) q.push(k); } } fillB(cent,b,vv[1].second); return ret; } fill(ret.begin(),ret.end(),0); return ret; }

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

split.cpp: In function 'int calc(int)':
split.cpp:21:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   21 |  vis[cur] = sz[cur] = 1;
      |             ~~~~~~~~^~~
#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...