#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#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) {
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]);
}
SDS(0);
for (int i = 0; i < n;i++) adj[i] = e[i];
bool 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();*/
dfs(0,-1,0);
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;
}
Compilation message
split.cpp: In function 'std::vector<int> case2()':
split.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (v.size() != n) {
~~~~~~~~~^~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:120:7: warning: unused variable 'G' [-Wunused-variable]
bool G= 1;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
812 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
769 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
836 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
784 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
812 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
