| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 426994 | saleh | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "split.h"
#include <bits/stdc++.h>
#define ft first
#define sd second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 100 * 1000 + 23;
int zz = -1, cc, sz[MAXN], par[MAXN];
vector<int> res;
bitset<MAXN> mark;
vector<int> g[MAXN];
void dfsa(int v) {
mark[v] = true;
zz = v;
cc--;
for (auto i : g[v]) if (!mark[i] && cc != 0) dfsa(i);
}
int sfs(int v = 0, int p = -1) {
par[v] = p;
for (auto i : g[v]) if (i != p) sz[v] += sfs(i, v);
return ++sz[v];
}
void mfs(int v, int p, int c) {
res[v] = c;
for (int i : g[v]) if (i != p) mfs(i, v, c);
}
void cfs(int v, int c) {
mark[v] = true;
cc--;
res[v] = c;
for (auto i : g[v]) if (!mark[i] && cc != 0) cfs(i, c);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size();
for (int i = 0; i < m; i++) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
if (a == 1) {
for (int i = 0; i < n; i++) res.push_back(3);
cc = b + 1;
dfsa(0);
for (int i = 0; i < n; i++) if (mark[i]) res[i] = 2;
res[zz] = 1;
return res;
}
if (m == n - 1) {
for (int i = 0; i < n; i++) res.push_back(0);
vector<pii> o = {{a, 1}, {b, 2}, {c, 3}};
sort(o.begin(), o.end());
int f = min({a, b, c}), g = max({min(a, b), min(b, c), min(c, a)});
sfs();
for (int i = 1; i < n; i++) if (sz[i] >= f && n - sz[a] >= g) {
cc = f;
mfs(i, par[i], o[0].sd);
cc = g;
mfs(par[i], i, o[1].sd);
for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = o[2].sd;
break;
} else if (sz[i] >= g && n - sz[a] >= f) {
cc = g;
mfs(i, par[i], o[1].sd);
cc = f;
mfs(par[i], i, o[0].sd);
for (int i = 0; i < n; i++) if (res[i] == 0) res[i] = o[2].sd;
break;
}
return res;
}
if (m == n) {
for (int i = 0; i < n; i++) res.push_back(0);
cc = a;
cfs(0, 1);
for (int i = 0; i < n; i++) if (!mark[i]) {
cc = b;
cfs(i, 2);
break;
}
for (int i = 0; i < n; i++) if (!mark[i]) {
cc = c;
cfs(i, 3);
break;
}
}
return res;
}
int main() {}