#include<bits/stdc++.h>
#include "split.h"
using namespace std;
const int MAX_SOM=100*1000+5;
int nbSom,nbAre,somPere,autreCompo,trouve,reste;
vector<int> rep;
vector<pair<int,int>> obj;
vector<int> adja[MAX_SOM];
int dv[MAX_SOM];
int prof[MAX_SOM];
int interdit[MAX_SOM];
int DFS(int pos) {
if (prof[pos]==0) {
prof[pos]=1;
for (int i:adja[pos]) {
prof[pos]+=DFS(i);
}
//cout<<pos<<" "<<prof[pos]<<endl;
return prof[pos];
}
return 0;
}
int calcDeb(int pos) {
for (int i:adja[pos]) {
if (prof[i]<prof[pos] and prof[i]>=obj[0].first) {
return calcDeb(i);
}
}
return pos;
}
void trouveMonte(int pos) {
if (dv[pos]==0) {
dv[pos]=1;
for (int i:adja[pos]) {
if (prof[i]>prof[somPere]) {
trouve=1;
}
else if (prof[i]<prof[pos]) {
trouveMonte(i);
}
}
}
}
void prop1(int pos) {
if (reste>0 and interdit[pos]==0 and rep[pos]==0) {
rep[pos]=obj[0].second;
reste--;
for (int i:adja[pos]) {
if (prof[i]<prof[pos]) {
prop1(i);
}
}
}
}
void prop2(int pos) {
if (reste>0 and rep[pos]==0) {
rep[pos]=obj[1].second;
reste--;
for (int i:adja[pos]) {
prop2(i);
}
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) {
nbSom=n;
nbAre=p.size();
obj={{a,1},{b,2},{c,3}};
sort(obj.begin(),obj.end());
rep.resize(nbSom);
for (int i=0;i<nbAre;i++) {
adja[p[i]].push_back(q[i]);
adja[q[i]].push_back(p[i]);
}
somPere=DFS(0);
somPere=calcDeb(0);
autreCompo=nbSom-prof[somPere];
//cout<<somPere<<endl;
for (int i:adja[somPere]) {
if (prof[i]<prof[somPere] and autreCompo<obj[0].first) {
trouve=0;
trouveMonte(i);
if (trouve==1) {
//cout<<i<<" ";
interdit[i]=1;
autreCompo+=prof[i];
}
}
}
//cout<<endl;
if (autreCompo<obj[0].first) {
return rep;
}
if (autreCompo<obj[1].first) {
swap(obj[0],obj[1]);
}
reste=obj[0].first;
prop1(somPere);
reste=obj[1].first;
prop2(0);
for (int i=0;i<nbSom;i++) {
if (rep[i]==0) {
rep[i]=obj[2].second;
}
}
return rep;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
ok, correct split |
2 |
Correct |
1 ms |
2644 KB |
ok, correct split |
3 |
Correct |
1 ms |
2644 KB |
ok, correct split |
4 |
Correct |
1 ms |
2644 KB |
ok, correct split |
5 |
Correct |
1 ms |
2644 KB |
ok, correct split |
6 |
Correct |
1 ms |
2644 KB |
ok, correct split |
7 |
Correct |
45 ms |
12872 KB |
ok, correct split |
8 |
Correct |
43 ms |
11636 KB |
ok, correct split |
9 |
Correct |
43 ms |
11128 KB |
ok, correct split |
10 |
Correct |
45 ms |
13180 KB |
ok, correct split |
11 |
Correct |
46 ms |
13140 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
ok, correct split |
2 |
Correct |
1 ms |
2644 KB |
ok, correct split |
3 |
Correct |
1 ms |
2644 KB |
ok, correct split |
4 |
Correct |
58 ms |
11760 KB |
ok, correct split |
5 |
Correct |
39 ms |
8572 KB |
ok, correct split |
6 |
Correct |
43 ms |
13132 KB |
ok, correct split |
7 |
Correct |
43 ms |
11508 KB |
ok, correct split |
8 |
Correct |
60 ms |
10812 KB |
ok, correct split |
9 |
Correct |
45 ms |
8556 KB |
ok, correct split |
10 |
Correct |
34 ms |
8816 KB |
ok, correct split |
11 |
Correct |
33 ms |
8908 KB |
ok, correct split |
12 |
Correct |
34 ms |
8908 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
ok, correct split |
2 |
Correct |
44 ms |
8564 KB |
ok, correct split |
3 |
Correct |
15 ms |
5076 KB |
ok, correct split |
4 |
Correct |
1 ms |
2644 KB |
ok, correct split |
5 |
Correct |
57 ms |
10196 KB |
ok, correct split |
6 |
Correct |
43 ms |
9932 KB |
ok, correct split |
7 |
Correct |
42 ms |
9712 KB |
ok, correct split |
8 |
Correct |
42 ms |
10572 KB |
ok, correct split |
9 |
Correct |
45 ms |
9712 KB |
ok, correct split |
10 |
Correct |
14 ms |
4796 KB |
ok, no valid answer |
11 |
Correct |
24 ms |
5840 KB |
ok, no valid answer |
12 |
Correct |
37 ms |
9060 KB |
ok, no valid answer |
13 |
Correct |
39 ms |
9036 KB |
ok, no valid answer |
14 |
Correct |
34 ms |
9200 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
ok, correct split |
2 |
Correct |
1 ms |
2644 KB |
ok, no valid answer |
3 |
Correct |
1 ms |
2644 KB |
ok, correct split |
4 |
Correct |
1 ms |
2644 KB |
ok, correct split |
5 |
Correct |
1 ms |
2644 KB |
ok, correct split |
6 |
Correct |
1 ms |
2644 KB |
ok, correct split |
7 |
Correct |
1 ms |
2644 KB |
ok, correct split |
8 |
Correct |
1 ms |
2644 KB |
ok, correct split |
9 |
Correct |
3 ms |
2900 KB |
ok, correct split |
10 |
Correct |
2 ms |
2772 KB |
ok, correct split |
11 |
Correct |
1 ms |
2644 KB |
ok, correct split |
12 |
Correct |
3 ms |
2772 KB |
ok, correct split |
13 |
Correct |
1 ms |
2644 KB |
ok, correct split |
14 |
Correct |
1 ms |
2644 KB |
ok, correct split |
15 |
Correct |
1 ms |
2644 KB |
ok, correct split |
16 |
Correct |
1 ms |
2644 KB |
ok, correct split |
17 |
Correct |
1 ms |
2644 KB |
ok, correct split |
18 |
Correct |
1 ms |
2644 KB |
ok, correct split |
19 |
Correct |
1 ms |
2644 KB |
ok, correct split |
20 |
Correct |
2 ms |
2644 KB |
ok, correct split |
21 |
Correct |
2 ms |
2772 KB |
ok, correct split |
22 |
Correct |
2 ms |
2772 KB |
ok, correct split |
23 |
Correct |
2 ms |
2772 KB |
ok, correct split |
24 |
Correct |
2 ms |
2772 KB |
ok, correct split |
25 |
Correct |
2 ms |
2772 KB |
ok, correct split |
26 |
Correct |
2 ms |
2772 KB |
ok, correct split |
27 |
Correct |
2 ms |
2772 KB |
ok, correct split |
28 |
Correct |
3 ms |
2772 KB |
ok, correct split |
29 |
Correct |
2 ms |
2644 KB |
ok, correct split |
30 |
Correct |
2 ms |
2772 KB |
ok, correct split |
31 |
Correct |
2 ms |
2644 KB |
ok, correct split |
32 |
Correct |
1 ms |
2644 KB |
ok, correct split |
33 |
Correct |
1 ms |
2644 KB |
ok, correct split |
34 |
Correct |
2 ms |
2772 KB |
ok, correct split |
35 |
Correct |
3 ms |
2744 KB |
ok, correct split |
36 |
Correct |
2 ms |
2772 KB |
ok, correct split |
37 |
Correct |
3 ms |
2880 KB |
ok, correct split |
38 |
Correct |
3 ms |
2820 KB |
ok, correct split |
39 |
Correct |
3 ms |
2772 KB |
ok, correct split |
40 |
Correct |
3 ms |
2772 KB |
ok, correct split |
41 |
Correct |
2 ms |
2644 KB |
ok, correct split |
42 |
Correct |
2 ms |
2644 KB |
ok, correct split |
43 |
Correct |
3 ms |
2772 KB |
ok, correct split |
44 |
Correct |
3 ms |
2840 KB |
ok, correct split |
45 |
Correct |
3 ms |
2772 KB |
ok, correct split |
46 |
Correct |
2 ms |
2780 KB |
ok, correct split |
47 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
48 |
Correct |
2 ms |
2772 KB |
ok, correct split |
49 |
Correct |
2 ms |
2772 KB |
ok, correct split |
50 |
Correct |
2 ms |
2644 KB |
ok, no valid answer |
51 |
Correct |
1 ms |
2644 KB |
ok, no valid answer |
52 |
Correct |
3 ms |
2900 KB |
ok, no valid answer |
53 |
Correct |
3 ms |
2772 KB |
ok, no valid answer |
54 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
55 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
56 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
ok, correct split |
2 |
Correct |
1 ms |
2644 KB |
ok, correct split |
3 |
Correct |
1 ms |
2644 KB |
ok, correct split |
4 |
Correct |
1 ms |
2644 KB |
ok, correct split |
5 |
Correct |
1 ms |
2644 KB |
ok, correct split |
6 |
Correct |
1 ms |
2644 KB |
ok, correct split |
7 |
Correct |
45 ms |
12872 KB |
ok, correct split |
8 |
Correct |
43 ms |
11636 KB |
ok, correct split |
9 |
Correct |
43 ms |
11128 KB |
ok, correct split |
10 |
Correct |
45 ms |
13180 KB |
ok, correct split |
11 |
Correct |
46 ms |
13140 KB |
ok, correct split |
12 |
Correct |
2 ms |
2644 KB |
ok, correct split |
13 |
Correct |
1 ms |
2644 KB |
ok, correct split |
14 |
Correct |
1 ms |
2644 KB |
ok, correct split |
15 |
Correct |
58 ms |
11760 KB |
ok, correct split |
16 |
Correct |
39 ms |
8572 KB |
ok, correct split |
17 |
Correct |
43 ms |
13132 KB |
ok, correct split |
18 |
Correct |
43 ms |
11508 KB |
ok, correct split |
19 |
Correct |
60 ms |
10812 KB |
ok, correct split |
20 |
Correct |
45 ms |
8556 KB |
ok, correct split |
21 |
Correct |
34 ms |
8816 KB |
ok, correct split |
22 |
Correct |
33 ms |
8908 KB |
ok, correct split |
23 |
Correct |
34 ms |
8908 KB |
ok, correct split |
24 |
Correct |
1 ms |
2644 KB |
ok, correct split |
25 |
Correct |
44 ms |
8564 KB |
ok, correct split |
26 |
Correct |
15 ms |
5076 KB |
ok, correct split |
27 |
Correct |
1 ms |
2644 KB |
ok, correct split |
28 |
Correct |
57 ms |
10196 KB |
ok, correct split |
29 |
Correct |
43 ms |
9932 KB |
ok, correct split |
30 |
Correct |
42 ms |
9712 KB |
ok, correct split |
31 |
Correct |
42 ms |
10572 KB |
ok, correct split |
32 |
Correct |
45 ms |
9712 KB |
ok, correct split |
33 |
Correct |
14 ms |
4796 KB |
ok, no valid answer |
34 |
Correct |
24 ms |
5840 KB |
ok, no valid answer |
35 |
Correct |
37 ms |
9060 KB |
ok, no valid answer |
36 |
Correct |
39 ms |
9036 KB |
ok, no valid answer |
37 |
Correct |
34 ms |
9200 KB |
ok, no valid answer |
38 |
Correct |
1 ms |
2644 KB |
ok, correct split |
39 |
Correct |
1 ms |
2644 KB |
ok, no valid answer |
40 |
Correct |
1 ms |
2644 KB |
ok, correct split |
41 |
Correct |
1 ms |
2644 KB |
ok, correct split |
42 |
Correct |
1 ms |
2644 KB |
ok, correct split |
43 |
Correct |
1 ms |
2644 KB |
ok, correct split |
44 |
Correct |
1 ms |
2644 KB |
ok, correct split |
45 |
Correct |
1 ms |
2644 KB |
ok, correct split |
46 |
Correct |
3 ms |
2900 KB |
ok, correct split |
47 |
Correct |
2 ms |
2772 KB |
ok, correct split |
48 |
Correct |
1 ms |
2644 KB |
ok, correct split |
49 |
Correct |
3 ms |
2772 KB |
ok, correct split |
50 |
Correct |
1 ms |
2644 KB |
ok, correct split |
51 |
Correct |
1 ms |
2644 KB |
ok, correct split |
52 |
Correct |
1 ms |
2644 KB |
ok, correct split |
53 |
Correct |
1 ms |
2644 KB |
ok, correct split |
54 |
Correct |
1 ms |
2644 KB |
ok, correct split |
55 |
Correct |
1 ms |
2644 KB |
ok, correct split |
56 |
Correct |
1 ms |
2644 KB |
ok, correct split |
57 |
Correct |
2 ms |
2644 KB |
ok, correct split |
58 |
Correct |
2 ms |
2772 KB |
ok, correct split |
59 |
Correct |
2 ms |
2772 KB |
ok, correct split |
60 |
Correct |
2 ms |
2772 KB |
ok, correct split |
61 |
Correct |
2 ms |
2772 KB |
ok, correct split |
62 |
Correct |
2 ms |
2772 KB |
ok, correct split |
63 |
Correct |
2 ms |
2772 KB |
ok, correct split |
64 |
Correct |
2 ms |
2772 KB |
ok, correct split |
65 |
Correct |
3 ms |
2772 KB |
ok, correct split |
66 |
Correct |
2 ms |
2644 KB |
ok, correct split |
67 |
Correct |
2 ms |
2772 KB |
ok, correct split |
68 |
Correct |
2 ms |
2644 KB |
ok, correct split |
69 |
Correct |
1 ms |
2644 KB |
ok, correct split |
70 |
Correct |
1 ms |
2644 KB |
ok, correct split |
71 |
Correct |
2 ms |
2772 KB |
ok, correct split |
72 |
Correct |
3 ms |
2744 KB |
ok, correct split |
73 |
Correct |
2 ms |
2772 KB |
ok, correct split |
74 |
Correct |
3 ms |
2880 KB |
ok, correct split |
75 |
Correct |
3 ms |
2820 KB |
ok, correct split |
76 |
Correct |
3 ms |
2772 KB |
ok, correct split |
77 |
Correct |
3 ms |
2772 KB |
ok, correct split |
78 |
Correct |
2 ms |
2644 KB |
ok, correct split |
79 |
Correct |
2 ms |
2644 KB |
ok, correct split |
80 |
Correct |
3 ms |
2772 KB |
ok, correct split |
81 |
Correct |
3 ms |
2840 KB |
ok, correct split |
82 |
Correct |
3 ms |
2772 KB |
ok, correct split |
83 |
Correct |
2 ms |
2780 KB |
ok, correct split |
84 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
85 |
Correct |
2 ms |
2772 KB |
ok, correct split |
86 |
Correct |
2 ms |
2772 KB |
ok, correct split |
87 |
Correct |
2 ms |
2644 KB |
ok, no valid answer |
88 |
Correct |
1 ms |
2644 KB |
ok, no valid answer |
89 |
Correct |
3 ms |
2900 KB |
ok, no valid answer |
90 |
Correct |
3 ms |
2772 KB |
ok, no valid answer |
91 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
92 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
93 |
Correct |
2 ms |
2772 KB |
ok, no valid answer |
94 |
Correct |
55 ms |
10444 KB |
ok, correct split |
95 |
Correct |
71 ms |
13828 KB |
ok, correct split |
96 |
Correct |
62 ms |
12688 KB |
ok, correct split |
97 |
Correct |
19 ms |
5076 KB |
ok, correct split |
98 |
Correct |
17 ms |
5076 KB |
ok, correct split |
99 |
Correct |
29 ms |
6868 KB |
ok, correct split |
100 |
Correct |
64 ms |
11300 KB |
ok, correct split |
101 |
Correct |
54 ms |
10316 KB |
ok, correct split |
102 |
Correct |
53 ms |
9904 KB |
ok, correct split |
103 |
Correct |
52 ms |
9796 KB |
ok, correct split |
104 |
Correct |
52 ms |
10992 KB |
ok, correct split |
105 |
Correct |
27 ms |
6760 KB |
ok, correct split |
106 |
Correct |
53 ms |
11636 KB |
ok, correct split |
107 |
Correct |
46 ms |
9384 KB |
ok, correct split |
108 |
Correct |
52 ms |
9008 KB |
ok, correct split |
109 |
Correct |
65 ms |
11580 KB |
ok, correct split |
110 |
Correct |
64 ms |
11132 KB |
ok, correct split |
111 |
Correct |
67 ms |
11004 KB |
ok, correct split |
112 |
Correct |
70 ms |
11556 KB |
ok, correct split |
113 |
Correct |
62 ms |
11288 KB |
ok, correct split |
114 |
Correct |
8 ms |
3732 KB |
ok, correct split |
115 |
Correct |
7 ms |
3540 KB |
ok, correct split |
116 |
Correct |
60 ms |
10740 KB |
ok, correct split |
117 |
Correct |
58 ms |
10728 KB |
ok, correct split |
118 |
Correct |
43 ms |
8532 KB |
ok, correct split |
119 |
Correct |
45 ms |
8564 KB |
ok, correct split |
120 |
Correct |
45 ms |
10940 KB |
ok, correct split |
121 |
Correct |
43 ms |
8908 KB |
ok, no valid answer |
122 |
Correct |
41 ms |
9068 KB |
ok, no valid answer |
123 |
Correct |
67 ms |
11776 KB |
ok, no valid answer |
124 |
Correct |
73 ms |
13944 KB |
ok, no valid answer |
125 |
Correct |
54 ms |
11192 KB |
ok, no valid answer |
126 |
Correct |
33 ms |
9640 KB |
ok, no valid answer |
127 |
Correct |
47 ms |
11828 KB |
ok, no valid answer |