#include "split.h"
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
using namespace std;
//#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define endl '\n'
using namespace std;
const int maxn = 2e5 + 10;
vi adj[maxn], tree[maxn], oth[maxn];
vi g[maxn];
int num[3], ans[maxn], sz[maxn], comp[maxn];
bool mark[maxn];
void dfs(int v){
mark[v] = 1;
for(auto u : adj[v]){
if(!mark[u]){
tree[v].push_back(u);
tree[u].push_back(v);
dfs(u);
}
else{
oth[u].push_back(v);
oth[v].push_back(u);
}
}
}
bool markTree[maxn];
void dfs_tree(int v,int root){
sz[v] = 1;
if(v == root)
memset(markTree, 0, sizeof markTree);
if(markTree[v])
return;
markTree[v] = 1;
for(auto u : tree[v]){
if(markTree[u])
continue;
if(v == root)
comp[u] = u;
else
comp[u] = comp[v];
dfs_tree(u, root);
sz[v] += sz[u];
}
}
int Rem;
void dfs_g(int v){
if(mark[v])
return;
mark[v] = 1;
Rem -= sz[v];
if(Rem <= 0) return;
for(auto u : g[v])
dfs_g(u);
}
int answer[maxn];
int rems = 0;
void dfs_ok(int v,int col){
if(mark[v] || ans[v] != col || rems <= 0)
return;
rems--;
answer[v] = col;
mark[v] = 1;
for(auto u : adj[v])
dfs_ok(u, col);
}
void make_ok(int n){
for(int i=0; i<n; i++)
answer[i] = 3;
rems = num[0];
memset(mark, 0, sizeof mark);
for(int i=0; i<n; i++)
if(ans[i] == 1){
dfs_ok(i, 1);
break;
}
rems = num[1];
memset(mark, 0, sizeof mark);
for(int i=0; i<n; i++)
if(ans[i] == 2){
dfs_ok(i, 2);
break;
}
}
vector<int> find_split(int n, int a1, int b1, int c1, vector<int> from, vector<int> to) {
int m = from.size();
num[0] = a1, num[1] = b1, num[2] = c1;
sort(num, num + 3);
for(int i=0; i<m; i++){
int u = from[i], v = to[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0);
dfs_tree(0, 0);
int root = 0;
while(1){
int bef = root;
for(auto u : tree[root]){
if(sz[u] > n/2)
root = u;
}
if(bef == root)
break;
}
memset(sz, 0, sizeof sz);
dfs_tree(root, root);
bool can = true;
if(m == n - 1){
can = false;
for(auto u : tree[root]){
if(sz[u] >= num[0]){
for(int i=0; i<n; i++)
ans[i] = (comp[i] == u ? 1 : 2);
can = true;
break;
}
}
make_ok(n);
}
else{
for(int i=0; i<n; i++){
ans[i] = 2;
for(auto j : oth[i]){
if(j != root && i != root){
int u = comp[i];
int v = comp[j];
if(u != v){
g[u].push_back(v);
g[v].push_back(u);
}
}
}
}
can = false;
for(auto u : tree[root]){
if(sz[u] >= num[0]){
for(int i=0; i<n; i++)
ans[i] = (comp[i] == u ? 1 : 2);
can = true;
break;
}
}
if(!can){
Rem = num[0];
memset(mark, 0, sizeof mark);
for(auto u : tree[root])
dfs_g(u);
for(int i=0; i<n; i++){
if(i != root && mark[comp[i]])
ans[i] = 1;
else
ans[i] = 2;
}
can = true;
}
make_ok(n);
}/*
cout << "CAN" << can << endl;
for(int i=0; i<n; i++)
cout << answer[i] << " ";
cout << endl;*/
pii per[3];
per[0] = {a1, 1};
per[1] = {b1, 2};
per[2] = {c1, 3};
sort(per, per + 3);
vi res;
res.resize(n);
if(can){
for(int i=0; i<n; i++)
res[i] = per[answer[i] - 1].Y;
}
return res;
}
/*
int main(){
int n, m;
cin >> n >> m;
int a1, b1, c1;
cin >> a1 >> b1 >> c1;
vi fr, to;
for(int i=0; i<m; i++){
int x, y;
cin >> x >> y;
fr.push_back(x);
to.push_back(y);
}
vi res = find_split(n, a1, b1, c1, fr, to);
for(auto t : res)
cout << t << " ";
cout << endl;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
20216 KB |
ok, correct split |
| 2 |
Execution timed out |
2071 ms |
19320 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
19320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2054 ms |
19320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
20344 KB |
ok, correct split |
| 2 |
Correct |
21 ms |
20344 KB |
ok, no valid answer |
| 3 |
Execution timed out |
2020 ms |
19292 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
20216 KB |
ok, correct split |
| 2 |
Execution timed out |
2071 ms |
19320 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
