| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 245179 | crossing0ver | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define local
#ifndef local
#include "split.h"
#endif
using namespace std;
const int MXN = 1e5 +5;
int n,a,b,c,m;
vector<int> adj[MXN];
vi case1() {
vector<bool> vis(n);
vis[0] = 1;
queue<int> q;
set<int> sec;
int cnt = b;
q.push(0);
while(!q.empty() && cnt) {
cnt--;
int v = q.front();
sec.insert(v);
q.pop();
for (int i :adj[v]) {
if (!vis[i]) {
vis[i] = 1;
q.push(i);
}
}
}
vector<int> ans(n);
for (int i : sec) ans[i] = 2;
for (int i = 0,flag = 0; i < n; i++) {
if (sec.count(i)) continue;
if (flag == 0) flag = 1, ans[i] = 1;
else ans[i] = 3;
}
return ans;
}
int sz[MXN],flag,X[4],mn;
set<int> ans[4];
void dfs(int v,int p,int type) {
if (type == 1 && X[flag]) {
X[flag]--;
ans[flag].insert(v);
}
sz[v] = 1;
for (int i : adj[v]) {
if (i == p) continue;
dfs(i,v,type);
sz[v] += sz[i];
}
if (flag) return;
if (sz[v] >= a && n - sz[v] >= min(b,c)) {
flag = 1;
if (n - sz[v] >= b) mn = 2;
else mn = 3;
}
else if (sz[v] >= b && n - sz[v] >= min(a,c)) {
flag = 2;
if (n - sz[v] >= a) mn = 1;
else mn = 3;
}
else if (sz[v] >= c && n - sz[v] >= min(a,b)) {
flag = 3;
if (n - sz[v] >= a) mn = 1;
else mn = 2;
}
else return;
dfs(v,p,1);
flag = mn;
if (p != -1)
dfs(p,v,1);
}
vi case2() {
int cnt = 0;
vi v,vis(n);
int cur = 0;
while(cnt != n) {
cnt++;
vis[cur] = 1;
v.push_back(cur);
for (int i : adj[cur]) {
if (vis[i]) continue;
cur = i;
break;
}
}
vi ans(n);
if (v.size() != n) {
while(true){
}
}
for (int i = 0; i < a;i++) ans[v[i]] = 1;
for (int i = a; i < a + b; i++) ans[v[i]] = 2;
for (int i = a+b; i < n; i++) ans[v[i]] = 3;
return ans;
}
int P[MXN],seen[MXN];
vi e[MXN];
void SDS(int v) {
seen[v] = 1;
for (int i : adj[v]) {
if (seen[i]) continue;
e[v].pb(i);
e[i].pb(v);
SDS(i);
}
}
vector<int> find_split(int n1, int a1, int b1, int c1, vector<int> p, vector<int> q) {
n = n1,a = a1,b=b1,c=c1;
X[1] = a,X[2] = b, X[3] = c;
m = p.size();
for (int i = 0;i < m; i++) {
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
int G = 1;
for (int i = 0; i < n;i++)
if (adj[i].size() != 2) G = 0;
if (G) return case2();
if (a == 1) return case1();
int lim = ( ( n <= 2500 && m <= 5000 ? ) n : 1)
for (int i = 0;i < lim; i++) {
dfs(i,-1,0);
if (flag) break;
}
vector<int> res(n),vis(n);
if (flag == 0) return res;
for (int j = 1; j <= 3; j++)
for (int i : ans[j]) res[i] = j,vis[i] = 1;
int id;
for (int i = 1; i <= 3; i++) if (ans[i].empty()) id = i;
for (int i = 0; i < n; i++) if (!vis[i]) res[i] = id;
return res;
}