#include "split.h"
#include<bits/stdc++.h>
#define lsb(x) (x&(-x))
using namespace std;
const int MAXN = 2e5 + 100;
using pii = pair<int,int>;
pii ord[3];
vector<int> res;
vector<int> grafo[MAXN];
vector<pii> edge;
int n;
int parent[MAXN];
int find(int id){
if(parent[id] == id) return id;
return parent[id] = find(parent[id]);
}
bool merge(int a,int b){
a = find(a);
b = find(b);
if(a == b) return false;
parent[a] = b;
return true;
}
void random_st(){
for(int i=0;i<n;i++){
grafo[i].clear();
parent[i] = i;
}
random_shuffle(edge.begin(),edge.end());
for(auto el : edge){
//cout<<el.first<<" "<<el.second<<endl;
if(merge(el.first,el.second)){
grafo[el.first].emplace_back(el.second);
grafo[el.second].emplace_back(el.first);
}
}
}
int block;
int req;
int rval;
int rid;
int dfs(int id,int prev){
//cout<<prev<<" => "<<id<<endl;
if(id == block) return 0;
int sum = 1;
for(auto el : grafo[id]){
if(el != prev){
sum += dfs(el,id);
}
}
if(sum >= req && sum < rval){
rval = sum;
rid = id;
}
return sum;
}
int p1,p2;
void f(int id,int prev,int stato){
if(id == p1) stato = 1;
if(id == p2) stato = 2;
switch(stato){
case 1:
if(ord[0].first){
ord[0].first--;
res[id] = ord[0].second;
}
break;
case 2:
if(ord[1].first){
ord[1].first--;
res[id] = ord[1].second;
}
break;
}
for(auto el : grafo[id]){
if(el != prev){
f(el,id,stato);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
res.resize(n);
::n = n;
ord[0] = {a, 1};
ord[1] = {b, 2};
ord[2] = {c, 3};
sort(ord,ord + 3);
edge.reserve(p.size());
for(int i=0;i<p.size();i++){
edge.emplace_back(p[i],q[i]);
}
for(int _=0;_<50;_++){
random_st();
int root = rand()%n;
rval = rid = 1e9;
block = -1;
req = ord[0].first;
dfs(root,-1);
//cout<<rid<<" - "<<rval<<endl;
if(rval == 1e9) continue;
p1 = rid;
rval = rid = 1e9;
block = p1;
req = ord[1].first;
dfs(root,-1);
//cout<<rid<<" - "<<rval<<endl;
p2 = rid;
//cout<<root<<" "<<p1<<" "<<p2<<endl;
if(p2 != 1e9){
f(root,-1,0);
for(auto&el:res){
if(!el) el = ord[2].second;
}
return res;
}
}
return res;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();i++){
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
6 ms |
4984 KB |
ok, correct split |
3 |
Correct |
6 ms |
4984 KB |
ok, correct split |
4 |
Correct |
6 ms |
4984 KB |
ok, correct split |
5 |
Correct |
6 ms |
4984 KB |
ok, correct split |
6 |
Correct |
6 ms |
4984 KB |
ok, correct split |
7 |
Correct |
130 ms |
16376 KB |
ok, correct split |
8 |
Correct |
163 ms |
16140 KB |
ok, correct split |
9 |
Correct |
130 ms |
15480 KB |
ok, correct split |
10 |
Correct |
155 ms |
16348 KB |
ok, correct split |
11 |
Correct |
137 ms |
14840 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
6 ms |
4984 KB |
ok, correct split |
3 |
Correct |
6 ms |
4984 KB |
ok, correct split |
4 |
Correct |
126 ms |
12920 KB |
ok, correct split |
5 |
Correct |
96 ms |
11780 KB |
ok, correct split |
6 |
Correct |
126 ms |
16248 KB |
ok, correct split |
7 |
Correct |
131 ms |
14996 KB |
ok, correct split |
8 |
Correct |
149 ms |
13816 KB |
ok, correct split |
9 |
Correct |
104 ms |
11768 KB |
ok, correct split |
10 |
Correct |
68 ms |
12016 KB |
ok, correct split |
11 |
Correct |
68 ms |
12160 KB |
ok, correct split |
12 |
Correct |
78 ms |
12016 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4988 KB |
ok, correct split |
2 |
Correct |
99 ms |
11744 KB |
ok, correct split |
3 |
Correct |
39 ms |
7800 KB |
ok, correct split |
4 |
Correct |
6 ms |
4984 KB |
ok, correct split |
5 |
Correct |
145 ms |
13724 KB |
ok, correct split |
6 |
Correct |
118 ms |
13540 KB |
ok, correct split |
7 |
Correct |
139 ms |
13816 KB |
ok, correct split |
8 |
Correct |
158 ms |
13816 KB |
ok, correct split |
9 |
Correct |
118 ms |
13560 KB |
ok, correct split |
10 |
Correct |
314 ms |
7416 KB |
ok, no valid answer |
11 |
Correct |
503 ms |
8552 KB |
ok, no valid answer |
12 |
Correct |
1010 ms |
12148 KB |
ok, no valid answer |
13 |
Correct |
1241 ms |
11896 KB |
ok, no valid answer |
14 |
Correct |
773 ms |
12272 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
6 ms |
4984 KB |
ok, no valid answer |
3 |
Correct |
7 ms |
4984 KB |
ok, correct split |
4 |
Correct |
6 ms |
4984 KB |
ok, correct split |
5 |
Correct |
6 ms |
4984 KB |
ok, correct split |
6 |
Correct |
6 ms |
4984 KB |
ok, correct split |
7 |
Correct |
7 ms |
4984 KB |
ok, correct split |
8 |
Correct |
6 ms |
4984 KB |
ok, correct split |
9 |
Correct |
9 ms |
5240 KB |
ok, correct split |
10 |
Correct |
10 ms |
5240 KB |
ok, correct split |
11 |
Correct |
7 ms |
4984 KB |
ok, correct split |
12 |
Incorrect |
29 ms |
5368 KB |
jury found a solution, contestant did not |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
6 ms |
4984 KB |
ok, correct split |
3 |
Correct |
6 ms |
4984 KB |
ok, correct split |
4 |
Correct |
6 ms |
4984 KB |
ok, correct split |
5 |
Correct |
6 ms |
4984 KB |
ok, correct split |
6 |
Correct |
6 ms |
4984 KB |
ok, correct split |
7 |
Correct |
130 ms |
16376 KB |
ok, correct split |
8 |
Correct |
163 ms |
16140 KB |
ok, correct split |
9 |
Correct |
130 ms |
15480 KB |
ok, correct split |
10 |
Correct |
155 ms |
16348 KB |
ok, correct split |
11 |
Correct |
137 ms |
14840 KB |
ok, correct split |
12 |
Correct |
6 ms |
4984 KB |
ok, correct split |
13 |
Correct |
6 ms |
4984 KB |
ok, correct split |
14 |
Correct |
6 ms |
4984 KB |
ok, correct split |
15 |
Correct |
126 ms |
12920 KB |
ok, correct split |
16 |
Correct |
96 ms |
11780 KB |
ok, correct split |
17 |
Correct |
126 ms |
16248 KB |
ok, correct split |
18 |
Correct |
131 ms |
14996 KB |
ok, correct split |
19 |
Correct |
149 ms |
13816 KB |
ok, correct split |
20 |
Correct |
104 ms |
11768 KB |
ok, correct split |
21 |
Correct |
68 ms |
12016 KB |
ok, correct split |
22 |
Correct |
68 ms |
12160 KB |
ok, correct split |
23 |
Correct |
78 ms |
12016 KB |
ok, correct split |
24 |
Correct |
6 ms |
4988 KB |
ok, correct split |
25 |
Correct |
99 ms |
11744 KB |
ok, correct split |
26 |
Correct |
39 ms |
7800 KB |
ok, correct split |
27 |
Correct |
6 ms |
4984 KB |
ok, correct split |
28 |
Correct |
145 ms |
13724 KB |
ok, correct split |
29 |
Correct |
118 ms |
13540 KB |
ok, correct split |
30 |
Correct |
139 ms |
13816 KB |
ok, correct split |
31 |
Correct |
158 ms |
13816 KB |
ok, correct split |
32 |
Correct |
118 ms |
13560 KB |
ok, correct split |
33 |
Correct |
314 ms |
7416 KB |
ok, no valid answer |
34 |
Correct |
503 ms |
8552 KB |
ok, no valid answer |
35 |
Correct |
1010 ms |
12148 KB |
ok, no valid answer |
36 |
Correct |
1241 ms |
11896 KB |
ok, no valid answer |
37 |
Correct |
773 ms |
12272 KB |
ok, no valid answer |
38 |
Correct |
6 ms |
4984 KB |
ok, correct split |
39 |
Correct |
6 ms |
4984 KB |
ok, no valid answer |
40 |
Correct |
7 ms |
4984 KB |
ok, correct split |
41 |
Correct |
6 ms |
4984 KB |
ok, correct split |
42 |
Correct |
6 ms |
4984 KB |
ok, correct split |
43 |
Correct |
6 ms |
4984 KB |
ok, correct split |
44 |
Correct |
7 ms |
4984 KB |
ok, correct split |
45 |
Correct |
6 ms |
4984 KB |
ok, correct split |
46 |
Correct |
9 ms |
5240 KB |
ok, correct split |
47 |
Correct |
10 ms |
5240 KB |
ok, correct split |
48 |
Correct |
7 ms |
4984 KB |
ok, correct split |
49 |
Incorrect |
29 ms |
5368 KB |
jury found a solution, contestant did not |
50 |
Halted |
0 ms |
0 KB |
- |