#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],graph[MXN];
void SDS(int v) {
seen[v] = 1;
for (int i : graph[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]);
}
for (int i = 0; i < n; i++)
graph[i] = adj[i];
for (int i = 0; i < n; i++) {
memset(seen,0,sizeof seen);
SDS(i);
for (int j = 1; j < 4;j++) ans[i].clear();
X[1] = a,X[2] = b, X[3] = c;
dfs(i,-1,0);
if (flag == 0) continue;
vector<int> res(n),vis(n);
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;
}
return vi(n,0);
}
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) {
~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7808 KB |
ok, correct split |
| 2 |
Runtime error |
769 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7808 KB |
ok, correct split |
| 2 |
Runtime error |
695 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
7808 KB |
ok, correct split |
| 2 |
Correct |
212 ms |
22904 KB |
ok, correct split |
| 3 |
Correct |
67 ms |
12792 KB |
ok, correct split |
| 4 |
Correct |
10 ms |
7808 KB |
ok, correct split |
| 5 |
Correct |
241 ms |
25080 KB |
ok, correct split |
| 6 |
Correct |
206 ms |
24824 KB |
ok, correct split |
| 7 |
Correct |
212 ms |
25592 KB |
ok, correct split |
| 8 |
Correct |
257 ms |
25848 KB |
ok, correct split |
| 9 |
Correct |
228 ms |
25336 KB |
ok, correct split |
| 10 |
Runtime error |
92 ms |
26360 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
703 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 |
Correct |
9 ms |
7808 KB |
ok, correct split |
| 2 |
Runtime error |
769 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
