#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;
mt19937 rng(132165);
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;
}
shuffle(edge.begin(),edge.end(),rng);
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;_<70;_++){
random_st();
int root = rng()%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:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();i++){
~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
5112 KB |
ok, correct split |
6 |
Correct |
6 ms |
5112 KB |
ok, correct split |
7 |
Correct |
117 ms |
15608 KB |
ok, correct split |
8 |
Correct |
164 ms |
15836 KB |
ok, correct split |
9 |
Correct |
142 ms |
15096 KB |
ok, correct split |
10 |
Correct |
123 ms |
15992 KB |
ok, correct split |
11 |
Correct |
105 ms |
14352 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
6 ms |
4984 KB |
ok, correct split |
3 |
Correct |
6 ms |
4960 KB |
ok, correct split |
4 |
Correct |
127 ms |
12924 KB |
ok, correct split |
5 |
Correct |
108 ms |
11868 KB |
ok, correct split |
6 |
Correct |
117 ms |
16072 KB |
ok, correct split |
7 |
Correct |
109 ms |
14840 KB |
ok, correct split |
8 |
Correct |
152 ms |
13944 KB |
ok, correct split |
9 |
Correct |
114 ms |
11768 KB |
ok, correct split |
10 |
Correct |
72 ms |
12096 KB |
ok, correct split |
11 |
Correct |
71 ms |
12144 KB |
ok, correct split |
12 |
Correct |
75 ms |
12144 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
97 ms |
11756 KB |
ok, correct split |
3 |
Correct |
38 ms |
7800 KB |
ok, correct split |
4 |
Correct |
6 ms |
4988 KB |
ok, correct split |
5 |
Correct |
128 ms |
13816 KB |
ok, correct split |
6 |
Correct |
161 ms |
13884 KB |
ok, correct split |
7 |
Correct |
111 ms |
13204 KB |
ok, correct split |
8 |
Correct |
108 ms |
13444 KB |
ok, correct split |
9 |
Correct |
119 ms |
13916 KB |
ok, correct split |
10 |
Correct |
419 ms |
7340 KB |
ok, no valid answer |
11 |
Correct |
676 ms |
8440 KB |
ok, no valid answer |
12 |
Correct |
1444 ms |
12228 KB |
ok, no valid answer |
13 |
Correct |
1809 ms |
12052 KB |
ok, no valid answer |
14 |
Correct |
1108 ms |
12016 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
6 ms |
4984 KB |
ok, no valid answer |
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 |
6 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 |
9 ms |
5256 KB |
ok, correct split |
11 |
Correct |
6 ms |
4984 KB |
ok, correct split |
12 |
Incorrect |
36 ms |
5240 KB |
jury found a solution, contestant did not |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
5112 KB |
ok, correct split |
6 |
Correct |
6 ms |
5112 KB |
ok, correct split |
7 |
Correct |
117 ms |
15608 KB |
ok, correct split |
8 |
Correct |
164 ms |
15836 KB |
ok, correct split |
9 |
Correct |
142 ms |
15096 KB |
ok, correct split |
10 |
Correct |
123 ms |
15992 KB |
ok, correct split |
11 |
Correct |
105 ms |
14352 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 |
4960 KB |
ok, correct split |
15 |
Correct |
127 ms |
12924 KB |
ok, correct split |
16 |
Correct |
108 ms |
11868 KB |
ok, correct split |
17 |
Correct |
117 ms |
16072 KB |
ok, correct split |
18 |
Correct |
109 ms |
14840 KB |
ok, correct split |
19 |
Correct |
152 ms |
13944 KB |
ok, correct split |
20 |
Correct |
114 ms |
11768 KB |
ok, correct split |
21 |
Correct |
72 ms |
12096 KB |
ok, correct split |
22 |
Correct |
71 ms |
12144 KB |
ok, correct split |
23 |
Correct |
75 ms |
12144 KB |
ok, correct split |
24 |
Correct |
6 ms |
4984 KB |
ok, correct split |
25 |
Correct |
97 ms |
11756 KB |
ok, correct split |
26 |
Correct |
38 ms |
7800 KB |
ok, correct split |
27 |
Correct |
6 ms |
4988 KB |
ok, correct split |
28 |
Correct |
128 ms |
13816 KB |
ok, correct split |
29 |
Correct |
161 ms |
13884 KB |
ok, correct split |
30 |
Correct |
111 ms |
13204 KB |
ok, correct split |
31 |
Correct |
108 ms |
13444 KB |
ok, correct split |
32 |
Correct |
119 ms |
13916 KB |
ok, correct split |
33 |
Correct |
419 ms |
7340 KB |
ok, no valid answer |
34 |
Correct |
676 ms |
8440 KB |
ok, no valid answer |
35 |
Correct |
1444 ms |
12228 KB |
ok, no valid answer |
36 |
Correct |
1809 ms |
12052 KB |
ok, no valid answer |
37 |
Correct |
1108 ms |
12016 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 |
6 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 |
6 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 |
9 ms |
5256 KB |
ok, correct split |
48 |
Correct |
6 ms |
4984 KB |
ok, correct split |
49 |
Incorrect |
36 ms |
5240 KB |
jury found a solution, contestant did not |
50 |
Halted |
0 ms |
0 KB |
- |