#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,m,ttl=0,nn=0,dsu[200069],dh[100069],pg[100069],sbt[300069],wg[100069],pr[100069],fh[100069],ca[100069],sq[100069];
pair<long long,long long> d[3],mdh[100069];
vector<pair<long long,long long>> al[100069];
bitset<300069> vtd;
bitset<100069> vtd2,spc;
vector<long long> al2[300069],sbl[300069],al3[100069];
multiset<long long> ms[100069];
bool bad=0,r0=0;
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void bct(long long x,long long b4)
{
long long i,sz=al[x].size(),l,p;
vtd[x]=1;
vtd2[x]=1;
mdh[x]={dh[x],-1};
for(i=0;i<sz;i++)
{
l=al[x][i].fr;
p=al[x][i].sc;
if(p==b4)
{
continue;
}
if(!vtd[l])
{
dh[l]=dh[x]+1;
pg[x]=p;
bct(l,p);
}
if(vtd2[l])
{
dsu[fd(p)]=fd(pg[l]);
mdh[x]=min(mdh[x],{dh[l],p});
}
else if(mdh[l].fr<=dh[x])
{
dsu[fd(p)]=fd(mdh[l].sc);
mdh[x]=min(mdh[x],{mdh[l].fr,p});
}
}
vtd2[x]=0;
}
void bd(long long x)
{
long long i,sz=al2[x].size(),l,e=-1;
vtd[x]=1;
sbt[x]=x<n;
for(i=0;i<sz;i++)
{
l=al2[x][i];
if(!vtd[l])
{
bd(l);
sbt[x]+=sbt[l];
}
else
{
e=l;
}
}
for(i=0;i<sz;i++)
{
l=al2[x][i];
if(l!=e)
{
sbl[x].push_back(sbt[l]);
}
else
{
sbl[x].push_back(n-sbt[x]);
}
}
}
void trv(long long x,long long xx)
{
long long i,sz=al[x].size(),l;
vtd[x]=1;
if(d[xx].fr)
{
sq[x]=d[xx].sc;
d[xx].fr--;
}
for(i=0;i<sz;i++)
{
l=al[x][i].fr;
if((!wg[l]||spc[l]==spc[x])&&!vtd[l])
{
trv(l,xx);
}
}
}
void dbd(long long x,long long b4)
{
long long i,sz=al[x].size(),l,p,mn=dh[x];
vtd[x]=1;
vtd2[x]=1;
fh[x]=dh[x];
for(i=0;i<sz;i++)
{
l=al[x][i].fr;
p=al[x][i].sc;
if(p==b4)
{
continue;
}
if(wg[l])
{
if(!vtd[l])
{
dh[l]=dh[x]+1;
pr[l]=x;
dbd(l,p);
fh[x]=min(fh[x],fh[l]);
al3[x].push_back(l);
ms[x].insert(fh[l]);
}
else if(vtd2[l])
{
fh[x]=min(fh[x],dh[l]);
al3[l].push_back(x);
mn=min(mn,dh[l]);
}
}
}
vtd2[x]=0;
ms[x].insert(mn);
}
bool cmp(long long x,long long y)
{
return dh[x]>dh[y];
}
void dtrv(long long x)
{
long long i,sz=al3[x].size(),l;
vtd[x]=1;
ttl+=wg[x];
spc[x]=1;
if(ttl>=d[0].fr)
{
r0=1;
return;
}
nn++;
ca[nn]=x;
sort(al3[x].begin(),al3[x].end(),cmp);
for(i=0;i<sz;i++)
{
l=al3[x][i];
if(!vtd[l]&&(fh[l]>=dh[x]||dh[l]==dh[x]+1))
{
dtrv(l);
if(r0)
{
return;
}
}
}
nn--;
if(pr[x]+1)
{
ms[pr[x]].erase(ms[pr[x]].find(fh[x]));
if(!vtd[pr[x]]&&(!nn||*ms[pr[x]].begin()>dh[ca[nn]]))
{
dtrv(pr[x]);
}
}
}
vector<int> find_split(int on,int od,int od2,int od3,vector<int> ka,vector<int> la)
{
long long i,j,ii,l,w,sz,p,e;
vector<long long> v;
vector<int> v2;
n=on;
d[0]={od,1};
d[1]={od2,2};
d[2]={od3,3};
sort(d,d+3);
m=ka.size();
for(i=0;i<m;i++)
{
al[ka[i]].push_back({la[i],i});
al[la[i]].push_back({ka[i],i});
dsu[i]=i;
}
bct(0,-1);
for(i=0;i<m;i++)
{
for(ii=0;ii<2;ii++)
{
al2[ka[i]].push_back(n+fd(i));
al2[n+fd(i)].push_back(ka[i]);
swap(ka[i],la[i]);
}
}
for(i=0;i<n+m;i++)
{
sort(al2[i].begin(),al2[i].end());
v.clear();
sz=al2[i].size();
for(j=0;j<sz;j++)
{
l=al2[i][j];
if(!j||l!=al2[i][j-1])
{
v.push_back(l);
}
}
al2[i]=v;
}
vtd.reset();
bd(0);
for(i=n;i<n+m;i++)
{
sz=al2[i].size();
for(j=0;j<sz;j++)
{
l=al2[i][j];
w=sbl[i][j];
for(ii=0;ii<2;ii++)
{
if(w>=d[ii].fr&&n-w>=d[!ii].fr)
{
p=l;
e=ii;
break;
}
}
if(ii<2)
{
break;
}
}
if(j<sz)
{
vtd.reset();
for(j=0;j<sz;j++)
{
l=al2[i][j];
vtd[l]=l!=p;
}
trv(p,e);
vtd.reset();
vtd[p]=1;
trv(al2[i][al2[i][0]==p],!e);
bad=1;
break;
}
}
if(!bad)
{
for(i=n;i<n+m;i++)
{
if(fd(i-n)==i-n)
{
sz=al2[i].size();
for(j=0;j<sz;j++)
{
w=sbl[i][j];
if(n-w<d[1].fr)
{
break;
}
}
if(j>=sz)
{
for(j=0;j<sz;j++)
{
l=al2[i][j];
w=sbl[i][j];
wg[l]=w;
}
vtd.reset();
dh[l]=0;
pr[l]=-1;
dbd(l,-1);
vtd.reset();
dtrv(al3[l][al3[l].size()-1]);
e=ttl<d[0].fr||n-ttl<d[1].fr;
vtd.reset();
for(ii=0;ii<2;ii++)
{
for(j=0;j<sz;j++)
{
l=al2[i][j];
if(spc[l]==!ii)
{
trv(l,ii^e);
break;
}
}
}
bad=1;
break;
}
}
}
}
for(i=0;i<n;i++)
{
if(bad&&!sq[i])
{
sq[i]=d[2].sc;
}
v2.push_back(sq[i]);
}
return v2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
31376 KB |
ok, correct split |
2 |
Correct |
8 ms |
31324 KB |
ok, correct split |
3 |
Correct |
7 ms |
31324 KB |
ok, correct split |
4 |
Correct |
7 ms |
31376 KB |
ok, correct split |
5 |
Correct |
8 ms |
31324 KB |
ok, correct split |
6 |
Correct |
7 ms |
33372 KB |
ok, correct split |
7 |
Correct |
215 ms |
70732 KB |
ok, correct split |
8 |
Correct |
221 ms |
65408 KB |
ok, correct split |
9 |
Correct |
195 ms |
63680 KB |
ok, correct split |
10 |
Correct |
137 ms |
66120 KB |
ok, correct split |
11 |
Correct |
225 ms |
80088 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
31320 KB |
ok, correct split |
2 |
Correct |
7 ms |
31324 KB |
ok, correct split |
3 |
Correct |
7 ms |
31356 KB |
ok, correct split |
4 |
Correct |
202 ms |
64580 KB |
ok, correct split |
5 |
Correct |
161 ms |
54184 KB |
ok, correct split |
6 |
Correct |
144 ms |
66064 KB |
ok, correct split |
7 |
Correct |
199 ms |
64788 KB |
ok, correct split |
8 |
Correct |
236 ms |
61916 KB |
ok, correct split |
9 |
Correct |
124 ms |
48448 KB |
ok, correct split |
10 |
Correct |
97 ms |
54900 KB |
ok, correct split |
11 |
Correct |
114 ms |
55452 KB |
ok, correct split |
12 |
Correct |
99 ms |
55600 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
31324 KB |
ok, correct split |
2 |
Correct |
188 ms |
54148 KB |
ok, correct split |
3 |
Correct |
54 ms |
40536 KB |
ok, correct split |
4 |
Correct |
7 ms |
31324 KB |
ok, correct split |
5 |
Correct |
253 ms |
58972 KB |
ok, correct split |
6 |
Correct |
217 ms |
58492 KB |
ok, correct split |
7 |
Correct |
256 ms |
58064 KB |
ok, correct split |
8 |
Correct |
206 ms |
61364 KB |
ok, correct split |
9 |
Correct |
205 ms |
57748 KB |
ok, correct split |
10 |
Correct |
46 ms |
38956 KB |
ok, no valid answer |
11 |
Correct |
70 ms |
42808 KB |
ok, no valid answer |
12 |
Correct |
124 ms |
55104 KB |
ok, no valid answer |
13 |
Correct |
180 ms |
54400 KB |
ok, no valid answer |
14 |
Correct |
97 ms |
55692 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
31160 KB |
ok, correct split |
2 |
Correct |
7 ms |
31324 KB |
ok, no valid answer |
3 |
Correct |
7 ms |
31324 KB |
ok, correct split |
4 |
Correct |
7 ms |
31360 KB |
ok, correct split |
5 |
Correct |
7 ms |
33372 KB |
ok, correct split |
6 |
Correct |
7 ms |
31324 KB |
ok, correct split |
7 |
Correct |
7 ms |
31324 KB |
ok, correct split |
8 |
Correct |
8 ms |
33372 KB |
ok, correct split |
9 |
Correct |
10 ms |
32092 KB |
ok, correct split |
10 |
Correct |
10 ms |
31980 KB |
ok, correct split |
11 |
Correct |
8 ms |
33516 KB |
ok, correct split |
12 |
Correct |
11 ms |
34372 KB |
ok, correct split |
13 |
Correct |
7 ms |
33372 KB |
ok, correct split |
14 |
Correct |
7 ms |
33372 KB |
ok, correct split |
15 |
Correct |
7 ms |
31320 KB |
ok, correct split |
16 |
Correct |
6 ms |
31324 KB |
ok, correct split |
17 |
Correct |
6 ms |
31324 KB |
ok, correct split |
18 |
Correct |
7 ms |
33440 KB |
ok, correct split |
19 |
Correct |
10 ms |
33368 KB |
ok, correct split |
20 |
Correct |
8 ms |
33628 KB |
ok, correct split |
21 |
Correct |
9 ms |
31836 KB |
ok, correct split |
22 |
Correct |
10 ms |
31836 KB |
ok, correct split |
23 |
Correct |
9 ms |
32092 KB |
ok, correct split |
24 |
Correct |
11 ms |
31836 KB |
ok, correct split |
25 |
Correct |
12 ms |
31844 KB |
ok, correct split |
26 |
Correct |
11 ms |
34136 KB |
ok, correct split |
27 |
Correct |
10 ms |
34140 KB |
ok, correct split |
28 |
Correct |
10 ms |
34172 KB |
ok, correct split |
29 |
Correct |
7 ms |
33372 KB |
ok, correct split |
30 |
Correct |
10 ms |
31836 KB |
ok, correct split |
31 |
Correct |
8 ms |
31580 KB |
ok, correct split |
32 |
Correct |
7 ms |
31324 KB |
ok, correct split |
33 |
Correct |
7 ms |
31320 KB |
ok, correct split |
34 |
Correct |
12 ms |
34084 KB |
ok, correct split |
35 |
Correct |
11 ms |
33884 KB |
ok, correct split |
36 |
Correct |
10 ms |
34140 KB |
ok, correct split |
37 |
Correct |
11 ms |
34396 KB |
ok, correct split |
38 |
Correct |
13 ms |
34452 KB |
ok, correct split |
39 |
Correct |
15 ms |
34396 KB |
ok, correct split |
40 |
Correct |
12 ms |
34268 KB |
ok, correct split |
41 |
Correct |
10 ms |
33812 KB |
ok, correct split |
42 |
Correct |
9 ms |
33884 KB |
ok, correct split |
43 |
Correct |
11 ms |
32092 KB |
ok, correct split |
44 |
Correct |
10 ms |
32092 KB |
ok, correct split |
45 |
Correct |
12 ms |
32092 KB |
ok, correct split |
46 |
Correct |
10 ms |
31992 KB |
ok, correct split |
47 |
Correct |
9 ms |
31836 KB |
ok, no valid answer |
48 |
Correct |
10 ms |
31836 KB |
ok, correct split |
49 |
Correct |
9 ms |
31836 KB |
ok, correct split |
50 |
Correct |
7 ms |
31324 KB |
ok, no valid answer |
51 |
Correct |
7 ms |
31324 KB |
ok, no valid answer |
52 |
Correct |
9 ms |
31836 KB |
ok, no valid answer |
53 |
Correct |
10 ms |
32092 KB |
ok, no valid answer |
54 |
Correct |
9 ms |
31840 KB |
ok, no valid answer |
55 |
Correct |
9 ms |
31836 KB |
ok, no valid answer |
56 |
Correct |
10 ms |
31868 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
31376 KB |
ok, correct split |
2 |
Correct |
8 ms |
31324 KB |
ok, correct split |
3 |
Correct |
7 ms |
31324 KB |
ok, correct split |
4 |
Correct |
7 ms |
31376 KB |
ok, correct split |
5 |
Correct |
8 ms |
31324 KB |
ok, correct split |
6 |
Correct |
7 ms |
33372 KB |
ok, correct split |
7 |
Correct |
215 ms |
70732 KB |
ok, correct split |
8 |
Correct |
221 ms |
65408 KB |
ok, correct split |
9 |
Correct |
195 ms |
63680 KB |
ok, correct split |
10 |
Correct |
137 ms |
66120 KB |
ok, correct split |
11 |
Correct |
225 ms |
80088 KB |
ok, correct split |
12 |
Correct |
7 ms |
31320 KB |
ok, correct split |
13 |
Correct |
7 ms |
31324 KB |
ok, correct split |
14 |
Correct |
7 ms |
31356 KB |
ok, correct split |
15 |
Correct |
202 ms |
64580 KB |
ok, correct split |
16 |
Correct |
161 ms |
54184 KB |
ok, correct split |
17 |
Correct |
144 ms |
66064 KB |
ok, correct split |
18 |
Correct |
199 ms |
64788 KB |
ok, correct split |
19 |
Correct |
236 ms |
61916 KB |
ok, correct split |
20 |
Correct |
124 ms |
48448 KB |
ok, correct split |
21 |
Correct |
97 ms |
54900 KB |
ok, correct split |
22 |
Correct |
114 ms |
55452 KB |
ok, correct split |
23 |
Correct |
99 ms |
55600 KB |
ok, correct split |
24 |
Correct |
7 ms |
31324 KB |
ok, correct split |
25 |
Correct |
188 ms |
54148 KB |
ok, correct split |
26 |
Correct |
54 ms |
40536 KB |
ok, correct split |
27 |
Correct |
7 ms |
31324 KB |
ok, correct split |
28 |
Correct |
253 ms |
58972 KB |
ok, correct split |
29 |
Correct |
217 ms |
58492 KB |
ok, correct split |
30 |
Correct |
256 ms |
58064 KB |
ok, correct split |
31 |
Correct |
206 ms |
61364 KB |
ok, correct split |
32 |
Correct |
205 ms |
57748 KB |
ok, correct split |
33 |
Correct |
46 ms |
38956 KB |
ok, no valid answer |
34 |
Correct |
70 ms |
42808 KB |
ok, no valid answer |
35 |
Correct |
124 ms |
55104 KB |
ok, no valid answer |
36 |
Correct |
180 ms |
54400 KB |
ok, no valid answer |
37 |
Correct |
97 ms |
55692 KB |
ok, no valid answer |
38 |
Correct |
7 ms |
31160 KB |
ok, correct split |
39 |
Correct |
7 ms |
31324 KB |
ok, no valid answer |
40 |
Correct |
7 ms |
31324 KB |
ok, correct split |
41 |
Correct |
7 ms |
31360 KB |
ok, correct split |
42 |
Correct |
7 ms |
33372 KB |
ok, correct split |
43 |
Correct |
7 ms |
31324 KB |
ok, correct split |
44 |
Correct |
7 ms |
31324 KB |
ok, correct split |
45 |
Correct |
8 ms |
33372 KB |
ok, correct split |
46 |
Correct |
10 ms |
32092 KB |
ok, correct split |
47 |
Correct |
10 ms |
31980 KB |
ok, correct split |
48 |
Correct |
8 ms |
33516 KB |
ok, correct split |
49 |
Correct |
11 ms |
34372 KB |
ok, correct split |
50 |
Correct |
7 ms |
33372 KB |
ok, correct split |
51 |
Correct |
7 ms |
33372 KB |
ok, correct split |
52 |
Correct |
7 ms |
31320 KB |
ok, correct split |
53 |
Correct |
6 ms |
31324 KB |
ok, correct split |
54 |
Correct |
6 ms |
31324 KB |
ok, correct split |
55 |
Correct |
7 ms |
33440 KB |
ok, correct split |
56 |
Correct |
10 ms |
33368 KB |
ok, correct split |
57 |
Correct |
8 ms |
33628 KB |
ok, correct split |
58 |
Correct |
9 ms |
31836 KB |
ok, correct split |
59 |
Correct |
10 ms |
31836 KB |
ok, correct split |
60 |
Correct |
9 ms |
32092 KB |
ok, correct split |
61 |
Correct |
11 ms |
31836 KB |
ok, correct split |
62 |
Correct |
12 ms |
31844 KB |
ok, correct split |
63 |
Correct |
11 ms |
34136 KB |
ok, correct split |
64 |
Correct |
10 ms |
34140 KB |
ok, correct split |
65 |
Correct |
10 ms |
34172 KB |
ok, correct split |
66 |
Correct |
7 ms |
33372 KB |
ok, correct split |
67 |
Correct |
10 ms |
31836 KB |
ok, correct split |
68 |
Correct |
8 ms |
31580 KB |
ok, correct split |
69 |
Correct |
7 ms |
31324 KB |
ok, correct split |
70 |
Correct |
7 ms |
31320 KB |
ok, correct split |
71 |
Correct |
12 ms |
34084 KB |
ok, correct split |
72 |
Correct |
11 ms |
33884 KB |
ok, correct split |
73 |
Correct |
10 ms |
34140 KB |
ok, correct split |
74 |
Correct |
11 ms |
34396 KB |
ok, correct split |
75 |
Correct |
13 ms |
34452 KB |
ok, correct split |
76 |
Correct |
15 ms |
34396 KB |
ok, correct split |
77 |
Correct |
12 ms |
34268 KB |
ok, correct split |
78 |
Correct |
10 ms |
33812 KB |
ok, correct split |
79 |
Correct |
9 ms |
33884 KB |
ok, correct split |
80 |
Correct |
11 ms |
32092 KB |
ok, correct split |
81 |
Correct |
10 ms |
32092 KB |
ok, correct split |
82 |
Correct |
12 ms |
32092 KB |
ok, correct split |
83 |
Correct |
10 ms |
31992 KB |
ok, correct split |
84 |
Correct |
9 ms |
31836 KB |
ok, no valid answer |
85 |
Correct |
10 ms |
31836 KB |
ok, correct split |
86 |
Correct |
9 ms |
31836 KB |
ok, correct split |
87 |
Correct |
7 ms |
31324 KB |
ok, no valid answer |
88 |
Correct |
7 ms |
31324 KB |
ok, no valid answer |
89 |
Correct |
9 ms |
31836 KB |
ok, no valid answer |
90 |
Correct |
10 ms |
32092 KB |
ok, no valid answer |
91 |
Correct |
9 ms |
31840 KB |
ok, no valid answer |
92 |
Correct |
9 ms |
31836 KB |
ok, no valid answer |
93 |
Correct |
10 ms |
31868 KB |
ok, no valid answer |
94 |
Correct |
242 ms |
67716 KB |
ok, correct split |
95 |
Correct |
364 ms |
86728 KB |
ok, correct split |
96 |
Correct |
350 ms |
81180 KB |
ok, correct split |
97 |
Correct |
59 ms |
40680 KB |
ok, correct split |
98 |
Correct |
64 ms |
40340 KB |
ok, correct split |
99 |
Correct |
82 ms |
46852 KB |
ok, correct split |
100 |
Correct |
219 ms |
62416 KB |
ok, correct split |
101 |
Correct |
193 ms |
59264 KB |
ok, correct split |
102 |
Correct |
200 ms |
59832 KB |
ok, correct split |
103 |
Correct |
171 ms |
59192 KB |
ok, correct split |
104 |
Correct |
137 ms |
60228 KB |
ok, correct split |
105 |
Correct |
106 ms |
48120 KB |
ok, correct split |
106 |
Correct |
192 ms |
72760 KB |
ok, correct split |
107 |
Correct |
132 ms |
56532 KB |
ok, correct split |
108 |
Correct |
167 ms |
55072 KB |
ok, correct split |
109 |
Correct |
211 ms |
64084 KB |
ok, correct split |
110 |
Correct |
300 ms |
77844 KB |
ok, correct split |
111 |
Correct |
285 ms |
78016 KB |
ok, correct split |
112 |
Correct |
249 ms |
74548 KB |
ok, correct split |
113 |
Correct |
259 ms |
75264 KB |
ok, correct split |
114 |
Correct |
26 ms |
38416 KB |
ok, correct split |
115 |
Correct |
26 ms |
37896 KB |
ok, correct split |
116 |
Correct |
178 ms |
62944 KB |
ok, correct split |
117 |
Correct |
202 ms |
62384 KB |
ok, correct split |
118 |
Correct |
117 ms |
49400 KB |
ok, correct split |
119 |
Correct |
123 ms |
49128 KB |
ok, correct split |
120 |
Correct |
146 ms |
57956 KB |
ok, correct split |
121 |
Correct |
144 ms |
53416 KB |
ok, no valid answer |
122 |
Correct |
200 ms |
52172 KB |
ok, no valid answer |
123 |
Correct |
223 ms |
61032 KB |
ok, no valid answer |
124 |
Correct |
273 ms |
60588 KB |
ok, no valid answer |
125 |
Correct |
130 ms |
57540 KB |
ok, no valid answer |
126 |
Correct |
85 ms |
53344 KB |
ok, no valid answer |
127 |
Correct |
224 ms |
58460 KB |
ok, no valid answer |