QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378219#4272. Phone PlansC1942huangjiaxu0 240ms108180kbC++142.9kb2024-04-06 09:49:352024-04-06 09:49:35

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 09:49:35]
  • 评测
  • 测评结果:0
  • 用时:240ms
  • 内存:108180kb
  • [2024-04-06 09:49:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5,inf=2e9+7;
int n,A,B,Sz[N],sz[N],fa[N],Fa[N][19],tot,ans=inf;
int dfn[N],in[N],out[N],nw,Rt,ln[N];
int rt[N],ls[N*40],rs[N*40],ct[N*40],cnt;
vector<int>e[N],w[N];
ll K,sum,va[N];
struct edge{
	int x,y,z;
	bool operator <(const edge a)const{return z<a.z;}
}ea[N],eb[N];
int gf(int x){
	return fa[x]==x?fa[x]:fa[x]=gf(fa[x]);
}
void dfs1(int x){
	for(int i=1;i<19;++i)Fa[x][i]=Fa[Fa[x][i-1]][i-1];
	if(x<=n){
		in[x]=out[x]=dfn[x]=++dfn[0];
		return;
	}
	in[x]=dfn[0];
	for(auto v:e[x])dfs1(v);
	out[x]=dfn[0];
}
void ins(int &k,int l,int r,int x){
	k=++cnt,ct[k]=1;
	if(l==r)return;
	int mid=l+r>>1;
	if(x<=mid)ins(ls[k],l,mid,x);
	else ins(rs[k],mid+1,r,x);
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	ls[x]=merge(ls[x],ls[y]);
	rs[x]=merge(rs[x],rs[y]);
	ct[x]=ct[x]+ct[y];
	return x;
}
int query(int k,int l,int r,int x,int y){
	if(!k)return 0;
	if(x<=l&&r<=y)return ct[k];
	int mid=l+r>>1,res=0;
	if(x<=mid)res+=query(ls[k],l,mid,x,y);
	if(y>mid)res+=query(rs[k],mid+1,r,x,y);
	return res;
}
void chg(int x){
	int c=gf(x),u=dfn[x];
	for(int i=18;~i;--i)if(Fa[x][i]&&Fa[x][i]<=nw)x=Fa[x][i];
	if(x<=n)return;
	sum-=query(rt[c],1,n,in[x],out[x]);
	if(out[e[x][0]]>=u)va[x]-=query(rt[c],1,n,in[e[x][1]],out[e[x][1]]);
	else va[x]-=query(rt[c],1,n,in[e[x][0]],out[e[x][0]]);
}
void dfs2(int x,int y){
	if(x<=n){
		va[Rt]-=query(rt[gf(x)],1,n,in[e[Rt][y]],out[e[Rt][y]]);
		return;
	}
	for(auto v:e[x])dfs2(v,y);
}
void calc(int x){
	if(x<=n)return;
	Rt=x;
	if(Sz[e[x][0]]<Sz[e[x][1]])dfs2(e[x][0],1);
	else dfs2(e[x][1],0);
	sum+=va[x];
}
int main(){
	scanf("%d%d%d%lld",&n,&A,&B,&K);
	tot=n;
	for(int i=1;i<=A;++i)scanf("%d%d%d",&ea[i].x,&ea[i].y,&ea[i].z);
	for(int i=1;i<=B;++i)scanf("%d%d%d",&eb[i].x,&eb[i].y,&eb[i].z);
	for(int i=1;i<=n;++i)Sz[i]=1,fa[i]=i;
	sort(ea+1,ea+A+1);
	sort(eb+1,eb+B+1);
	for(int i=1;i<=A;++i){
		int x=gf(ea[i].x),y=gf(ea[i].y);
		if(x==y)continue;
		++tot,e[tot].push_back(x),e[tot].push_back(y);
		Sz[tot]=Sz[x]+Sz[y];
		ln[tot]=ea[i].z;
		sum+=(va[tot]=1ll*Sz[x]*Sz[y]);
		fa[x]=fa[y]=Fa[x][0]=Fa[y][0]=fa[tot]=tot;
	}
	for(int i=tot;i;--i)if(!Fa[i][0])dfs1(i);
	for(int i=1;i<=n;++i)ins(rt[i],1,n,dfn[i]);
	nw=tot;
	while(nw>n&&sum-va[nw]>=K){
		sum-=va[nw];
		calc(e[nw][0]);
		calc(e[nw][1]);
		--nw;
	}
	if(sum>=K)ans=ln[nw];
	for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1,w[i].emplace_back(i);
	for(int i=1;i<=B;++i){
		int x=gf(eb[i].x),y=gf(eb[i].y);
		if(x==y)continue;
		if(sz[x]>sz[y])swap(x,y);
		sum+=1ll*sz[x]*sz[y];
		fa[x]=y,sz[y]+=sz[x];
		for(auto v:w[x])chg(v),w[y].emplace_back(v);
		rt[y]=merge(rt[y],rt[x]);
		while(nw>n&&sum-va[nw]>=K){
			sum-=va[nw];
			calc(e[nw][0]);
			calc(e[nw][1]);
			--nw;
		}
		if(sum>=K)ans=min(ans,eb[i].z+ln[nw]);
	}
	if(ans==inf)puts("-1");
	else printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 0ms
memory: 24436kb

input:

6 4 4 9
1 2 1
2 3 2
1 4 3
3 4 4
5 6 40
1 5 30
2 6 20
3 6 10

output:

33

result:

ok single line: '33'

Test #2:

score: 0
Accepted
time: 0ms
memory: 24312kb

input:

1 0 0 0

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 24220kb

input:

2 0 0 1

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 4ms
memory: 24436kb

input:

2 10 10 1
1 1 915886339
2 2 430624192
1 1 879808770
1 2 577221915
1 1 439429731
1 2 304911826
1 1 148009333
1 2 51122687
1 1 558282772
1 2 421196385
2 1 436692145
1 2 654020563
2 2 162573477
2 2 989531779
1 1 646687051
2 2 549037477
2 2 699532275
1 1 679375858
2 1 83352965
2 1 415698228

output:

51122687

result:

ok single line: '51122687'

Test #5:

score: 0
Accepted
time: 4ms
memory: 24352kb

input:

2 10 10 1
1 1 1000000000
1 2 1000000000
2 2 1000000000
2 1 1000000000
1 2 1000000000
1 1 1000000000
1 2 1000000000
2 2 1000000000
1 2 1000000000
1 2 1000000000
2 1 1000000000
1 2 1000000000
2 1 1000000000
2 2 1000000000
1 2 1000000000
2 2 1000000000
1 1 1000000000
1 1 1000000000
2 2 1000000000
1 2 1...

output:

1000000000

result:

ok single line: '1000000000'

Test #6:

score: 0
Accepted
time: 43ms
memory: 27256kb

input:

2000 0 200000 1199833
636 1231 120395621
689 1640 497332138
1861 1980 798839749
560 1283 560726905
1332 328 431171189
1203 1764 466367210
1102 347 317109768
1462 789 761470540
350 1093 551905741
1718 1047 548650524
51 546 56733461
58 1519 744207013
826 956 943929583
1969 207 238061756
99 47 99683567...

output:

9768257

result:

ok single line: '9768257'

Test #7:

score: -6
Wrong Answer
time: 44ms
memory: 29428kb

input:

2000 200000 0 1937051
1325 1770 628367155
105 1670 728177982
358 778 959944062
826 1691 651665248
1119 1906 382208628
1684 1232 677646622
807 265 902880211
1685 1660 405567549
1853 1982 988679307
1241 1054 385406922
862 1049 356441384
1837 673 443580113
1082 1795 738355567
1703 663 221254144
1792 84...

output:

0

result:

wrong answer 1st lines differ - expected: '20263921', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #53:

score: 0
Wrong Answer
time: 182ms
memory: 108180kb

input:

200000 100000 100000 7628995
23677 113459 839167193
165893 15365 669621527
26287 109671 214795757
156871 136723 522277985
9957 100463 806718116
104783 161385 156110975
184577 92225 545172629
57373 130083 980035338
167231 49597 919886451
115601 24325 717233004
99413 141311 737488449
83437 62759 76873...

output:

0

result:

wrong answer 1st lines differ - expected: '502149991', found: '0'

Subtask #3:

score: 0
Wrong Answer

Test #103:

score: 6
Accepted
time: 3ms
memory: 24376kb

input:

1 0 0 0

output:

0

result:

ok single line: '0'

Test #104:

score: 0
Accepted
time: 0ms
memory: 24356kb

input:

2 0 0 1

output:

-1

result:

ok single line: '-1'

Test #105:

score: 0
Accepted
time: 41ms
memory: 26120kb

input:

2 10 200000 1
2 1 319832429
1 1 412617159
2 1 337734185
1 2 674652880
1 2 454610992
2 2 688717944
1 1 189208056
2 2 951221780
1 2 594191431
2 2 87592160
1 2 833491749
2 2 732961971
2 1 575969648
2 2 268359887
2 1 436382098
1 2 514959278
1 2 305446083
1 2 365989813
1 2 296840111
1 1 541558213
1 1 497...

output:

10104

result:

ok single line: '10104'

Test #106:

score: 0
Accepted
time: 22ms
memory: 26900kb

input:

2 10 200000 1
1 1 1000000000
1 1 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 1 1000000000
2 1 1000000000
2 2 1000000000
2 2 1000000000
2 2 1000000000
1 1 1000000000
1 2 1000000000
1 1 1000000000
2 1 1000000000
1 1 1000000000
1 1 1000000000
2 1 1000000000
1 1 1000000000
2 2 1000000000
2...

output:

1000000000

result:

ok single line: '1000000000'

Test #107:

score: 0
Accepted
time: 217ms
memory: 99920kb

input:

200000 10 200000 17900
199675 76237 290240030
50211 6922 761990536
92097 120746 607490
192856 130409 616541101
50427 80049 330957286
129588 180294 466199684
8674 110653 155297749
91380 156344 798960399
102127 40858 801752583
94673 105892 152356242
185676 6183 263664373
169026 112948 812501808
93517 ...

output:

75425485

result:

ok single line: '75425485'

Test #108:

score: 0
Accepted
time: 209ms
memory: 98608kb

input:

200000 10 200000 11791021341
90115 14234 985783971
123477 154651 628493605
123171 47179 220847663
8072 163826 30383173
174753 12792 15862638
172837 96919 880800330
92696 166466 443031361
85298 185851 999558577
23737 111350 809362300
24551 127050 920973896
121483 145215 67814677
78536 41919 475800490...

output:

949367959

result:

ok single line: '949367959'

Test #109:

score: 0
Accepted
time: 240ms
memory: 98216kb

input:

200000 0 200000 423432
117280 87297 405090778
161764 93979 279208002
169095 190396 237565477
5136 81072 251360373
177384 130645 595157997
5282 38206 898866303
150431 96891 829055730
18413 42187 599085995
75585 47004 557307885
92187 77157 349172549
63029 186638 993483250
37685 198246 538754012
119056...

output:

404806867

result:

ok single line: '404806867'

Test #110:

score: 0
Accepted
time: 23ms
memory: 94992kb

input:

200000 10 0 1583868
66186 49114 583417488
79347 122356 957296935
4161 178945 973881307
39875 85386 62804962
62164 81798 964069340
6410 188411 31431750
67426 6153 513781110
49101 116783 513947988
61043 89483 259723608
14116 90504 23294861

output:

-1

result:

ok single line: '-1'

Test #111:

score: 0
Accepted
time: 219ms
memory: 96100kb

input:

200000 10 200000 19999900000
47625 147346 8
147346 121067 9
97009 179826 2
155552 97009 1
179826 22149 3
15370 4310 5
135552 47625 7
121067 131030 10
4310 135552 6
22149 15370 4
92707 136627 90227
20274 369 174990
32793 164281 194588
56508 95231 92612
117675 125225 114617
42843 81551 39780
149173 15...

output:

199999

result:

ok single line: '199999'

Test #112:

score: 0
Accepted
time: 227ms
memory: 97392kb

input:

200000 10 200000 19999900000
45665 143462 7
22696 184210 2
38538 57388 9
184210 154285 3
125307 22696 1
149825 71332 5
143462 38538 8
154285 149825 4
57388 182077 10
71332 45665 6
163095 156887 174710
77920 77020 63954
85503 109613 119638
46319 118285 60934
66569 45264 83574
73519 101885 163357
1583...

output:

200000

result:

ok single line: '200000'

Test #113:

score: 0
Accepted
time: 226ms
memory: 96864kb

input:

200000 10 200000 19999900000
739 28876 199992
53663 1295 199998
43161 52504 200000
158247 739 199993
2816 184328 199996
52504 53663 199999
1295 2816 199997
52726 158247 199994
28876 8395 199991
184328 52726 199995
130045 124454 95456
117404 39359 188185
42676 84681 4828
105147 95150 194669
17107 579...

output:

199999

result:

ok single line: '199999'

Test #114:

score: 0
Accepted
time: 223ms
memory: 98416kb

input:

200000 10 200000 19999900000
19794 183474 199991
71973 145759 199999
167290 188987 199995
6730 167290 199996
92616 6730 199997
93098 157369 199993
145759 92616 199998
104691 71973 200000
157369 19794 199992
188987 93098 199994
4529 33398 169717
116172 158258 118532
69720 25407 140713
173220 192301 1...

output:

200000

result:

ok single line: '200000'

Test #115:

score: 0
Accepted
time: 19ms
memory: 93740kb

input:

200000 0 0 0

output:

0

result:

ok single line: '0'

Test #116:

score: 0
Accepted
time: 24ms
memory: 94436kb

input:

200000 0 0 1

output:

-1

result:

ok single line: '-1'

Test #117:

score: 0
Accepted
time: 30ms
memory: 93232kb

input:

200000 0 0 19999900000

output:

-1

result:

ok single line: '-1'

Test #118:

score: 0
Accepted
time: 232ms
memory: 97448kb

input:

200000 10 200000 0
146668 190255 646706475
71516 174249 65976309
173393 55930 434227341
38682 164404 792088710
68045 174249 105770742
190255 24008 378601596
68045 174249 584120597
68045 68045 891140070
71516 71516 121444300
24008 173393 638520585
42552 123134 440551564
172416 148702 205154389
80345 ...

output:

0

result:

ok single line: '0'

Test #119:

score: -6
Wrong Answer
time: 233ms
memory: 97388kb

input:

200000 10 200000 1
18089 125148 634373061
26320 138377 746998187
125148 130407 287480602
136290 4926 478063834
136333 147458 29423436
26320 147458 334115471
4926 136290 505364255
18089 26320 866606210
11249 77957 605205962
136333 11249 440411926
170380 191070 819377443
150060 41355 635345633
143709 ...

output:

0

result:

wrong answer 1st lines differ - expected: '2407', found: '0'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%