QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100172#185. BridgesBronya0 1976ms14952kbC++202.7kb2023-04-24 20:57:452023-04-24 20:57:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-24 20:57:49]
  • 评测
  • 测评结果:0
  • 用时:1976ms
  • 内存:14952kb
  • [2023-04-24 20:57:45]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
int n,m,Q;
struct edge{
	int u,v;
	int a,b;
}e[200005];
int id[200005];
int ans[200005];
bool cmpp(int x,int y){
	return (e[x].b<e[y].b);
}
struct bcj{
	int siz;
	int len;
}val[200005];
int fa[200005];
stack<pair<int,bcj>>rc;
int Find(int u){
	return (fa[u]!=u?Find(fa[u]):u);
}
inline void merge(int u,int v){
	u=Find(u),v=Find(v);
	if(val[u].len<val[v].len)swap(u,v);
	if(u!=v){
		fa[v]=u;
		rc.push(make_pair(v,val[u]));
	}
	else rc.push(make_pair(u,val[u]));
	if(u!=v)val[u].siz+=val[v].siz,val[u].len=max(val[v].len+1,val[u].len);
}
inline void del(int u){
	while(rc.size()>u){
		int v=rc.top().first;
		val[fa[v]]=rc.top().second;
		fa[v]=v;
		rc.pop();
	}
}
set<pair<int,int> >hav;
vector<int>A;
vector<int>B;
int main(){
	// freopen("1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].b);e[i].b=-e[i].b;
		id[i]=i;
	}
	scanf("%d",&Q);
	for(int i=1;i<=m;i++)e[i].a=m+Q+1;
	for(int i=1;i<=Q;i++){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int u;
			scanf("%d",&u);
			e[i+m]=e[id[u]];
			e[id[u]].a=i+m-1;
			scanf("%d",&e[i+m].b);e[i+m].b=-e[i+m].b;
			id[u]=i+m;
		}
		else scanf("%d%d",&e[i+m].u,&e[i+m].b),e[i+m].a=-1,e[i+m].b=-e[i+m].b;
	}
//	for(int i=1;i<=m+Q;i++)cout<<e[i].a<<endl;
	for(int i=1;i<=n;i++)fa[i]=i,val[i].siz=1;
	int siz=sqrt(m*__lg(m));
	for(int i=1;(i-1)*siz+1<=m+Q;i++){
		A.clear();B.clear();
		for(auto j=hav.begin();j!=hav.end();j++){
			int u=j->second;
			if(e[u].a<=min(i*siz,m+Q))A.push_back(u);
		}
		for(int j=0;j<A.size();j++)hav.erase(hav.lower_bound(make_pair(e[A[j]].b,A[j])));
		for(int j=(i-1)*siz+1;j<=min(i*siz,m+Q);j++){
			if(e[j].a==-1)B.push_back(j);
			else A.push_back(j);
		}
		sort(B.begin(),B.end(),cmpp);
		int L=0;
		// cout<<L<<" "<<B.size()<<endl;
		for(auto j=hav.begin();j!=hav.end();j++){
			while(L<B.size()&&e[B[L]].b<j->first){
				int now=rc.size();
				for(int k=0;k<A.size();k++)
					if(A[k]<=B[L]&&e[A[k]].a>=B[L]&&e[A[k]].b<=e[B[L]].b)
						merge(e[A[k]].u,e[A[k]].v);
				int f1=Find(e[B[L]].u);
				ans[B[L]]=val[f1].siz;
				del(now);
				L++;
			}
			merge(e[j->second].u,e[j->second].v);
		}
		while(L<B.size()){
			int now=rc.size();
			for(int k=0;k<A.size();k++)
				if(A[k]<=B[L]&&e[A[k]].a>=B[L]&&e[A[k]].b<=e[B[L]].b)
					merge(e[A[k]].u,e[A[k]].v);
			int f1=Find(e[B[L]].u);
			ans[B[L]]=val[f1].siz;
			del(now);
			L++;
		}
		del(0);
		for(int j=0;j<A.size();j++){
			if(e[A[j]].a<=i*siz)continue;
			else hav.insert(make_pair(e[A[j]].b,A[j]));
		}	
	}
	for(int i=1;i<=m+Q;i++)
		if(e[i].a==-1)printf("%d\n",ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 13
Accepted
time: 2ms
memory: 3648kb

input:

3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2

output:

3
2
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3

output:

1
7
7
5
7
7
4

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 3712kb

input:

5 5
5 3 81
2 4 49
4 1 63
4 3 74
1 2 85
10
2 2 22
2 2 20
1 3 49
2 1 77
1 3 44
1 1 6
2 3 49
2 4 31
2 2 54
2 2 7

output:

5
5
2
4
4
2
4

result:

ok 7 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 3660kb

input:

5 10
1 3 51
1 2 74
2 4 63
1 4 86
2 5 9
5 1 28
5 4 1
2 1 23
2 5 16
3 1 75
10
2 2 37
1 6 24
1 1 24
2 5 65
1 7 57
2 1 82
2 1 26
1 4 12
2 2 15
1 4 70

output:

4
1
2
5
5

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 17ms
memory: 3924kb

input:

100 1000
26 42 977322268
4 29 374382133
1 19 717262653
80 56 835233390
58 54 591443635
63 6 579687470
85 81 118110131
33 100 533388119
24 46 591205239
94 32 637495476
60 93 638216409
55 7 413175730
38 43 414269997
48 30 773236579
67 27 441100383
44 36 784705206
28 56 300064078
13 60 490548719
94 19 ...

output:

100
100
100
100
100
100
100
100
17
100
100
100
100
100
5
100
98
100
100
100
100
100
100
100
100
100
100
100
100
96
100
2
42
100
100
100
86
97
100
100
100
98
100
100
100
100
100
97
100
100
100
100
100
100
100
100
100
100
100
100
100
98
100
100
100
100
100
5
100
100
100
100
100
98
100
100
100
100
1
10...

result:

ok 4938 lines

Test #6:

score: -13
Time Limit Exceeded

input:

1 0
10000
2 1 198824732
2 1 485321921
2 1 632483476
2 1 51814372
2 1 599796663
2 1 786502474
2 1 231528808
2 1 911511073
2 1 372581312
2 1 168699670
2 1 155928174
2 1 636544973
2 1 221309003
2 1 934838177
2 1 927074369
2 1 66460573
2 1 854380894
2 1 763039163
2 1 203254324
2 1 525763932
2 1 58538356...

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #20:

score: 16
Accepted
time: 1285ms
memory: 11212kb

input:

50000 49999
1 2 976392398
2 3 773336157
3 4 849545817
4 5 194340376
5 6 386778507
6 7 40561907
7 8 260116638
8 9 85673124
9 10 149683208
10 11 724746156
11 12 155084527
12 13 416939763
13 14 753621724
14 15 384948880
15 16 625917615
16 17 833747431
17 18 764302034
18 19 4518648
19 20 405679793
20 21...

output:

7
2
24
1
3
8
1
2
6
2
535
4
3
2
7
13
40
110
3
41
6
1
108
491
28
1
1
4
2
11
5
9
2
1
2
1
9
1
1
3
1
14
3
1
1
10
44
3
2
3
3
1
1
18
3
2
2
2
1
9
1
15
17
7
1
1
1
4
1
2
6
3
1
1
5
1
10
1
5
2
1
14
14
3
28
17
1
6
1
3
1
9
3
10
2
32
54
4
1
2
2
18
1
1
5
1
11
2
10
1
2
5
4
1
1
2
3
4
1
1
128
17
3
1
2
2
1
160
1
1
2
3
...

result:

ok 49863 lines

Test #21:

score: 0
Accepted
time: 1294ms
memory: 10232kb

input:

50000 49999
1 2 491
2 3 15360
3 4 24312
4 5 17754
5 6 40601
6 7 30620
7 8 69533
8 9 144923
9 10 304551
10 11 264913
11 12 265173
12 13 135700
13 14 61571
14 15 6841
15 16 413217
16 17 596083
17 18 157633
18 19 68400
19 20 348725
20 21 494086
21 22 327898
22 23 569190
23 24 195301
24 25 402492
25 26 ...

output:

6
7
16
2
13
24
24
8
1
3
5
257
1
3
6
1
112
2
5
2
11
1
6
2
6
1
1
4
177
7
19
1
1
42
10
2
25
4
24
4
1
3
3
2
1
1
5
1
3
2
13
1
1
1
2
3
5
3
9
2
16
4
10
6
7
3
1
2
17
37
3
1
4
1
4
1
3
7
1
2
2
1
135
3
34
5
2
2
8
2
1
1
1
1
4
3
1
3
2
5
2
1
5
1
2
5
503
3
1
9
7
1
2
4
2
3
5
9
2
15
3
7
9
16
1
28
5
2
5
4
2
3
8
9
4
1...

result:

ok 49979 lines

Test #22:

score: 0
Accepted
time: 1240ms
memory: 10164kb

input:

50000 49999
1 2 20928
2 3 33937
3 4 35582
4 5 123172
5 6 100214
6 7 105156
7 8 46684
8 9 124995
9 10 13728
10 11 209960
11 12 206098
12 13 146953
13 14 370445
14 15 141005
15 16 536276
16 17 80350
17 18 258276
18 19 401626
19 20 32874
20 21 125207
21 22 357075
22 23 598244
23 24 46414
24 25 609917
2...

output:

3
1
1
1
2
1
2
10
7
1
43
3
6
1
4
1
8
1
82
5
3
1
1
2
1
11
5
45
21
1
1
10
2
5
8
2
1
12
1
29
2
1
4
5
2
56
3
3
3
14
1
1
29
9
160
4
3
5
2
2
1
2
6
3
2
11
2
8
1
8
3
3
9
199
1
1
1
1
1
1
1
11
23
2
2
9
339
2
2
1
2
3
1
1
116
6
5
5
10
3
1
1
2
1
18
1
1
6
1
1
8
3
3
1
1
24
1
1
3
1
1
5
12
10
1
6
1
3
2
4
1
2
1
5
6
1
...

result:

ok 50005 lines

Test #23:

score: 0
Accepted
time: 1342ms
memory: 10168kb

input:

50000 49999
1 2 111167988
2 3 402479521
3 4 873342766
4 5 303335487
5 6 357259867
6 7 944570848
7 8 227864068
8 9 137899415
9 10 782881158
10 11 545137901
11 12 125756079
12 13 713912399
13 14 516355545
14 15 306731193
15 16 244028251
16 17 175980262
17 18 956260270
18 19 92690286
19 20 344996907
20...

output:

1
8
1
1
1
1
6
11
21
12
5
3
105
1
1
2
4
5
1
16
1
2
1
3
1
3
2
1
1
2
1
30
2
29
9
8
6
16
1
24
5
8
2
1
5
33
10
12
5
28
10
2
1
1
6
1
2
1
1
1
1
17
7
12
2
3
10
6
2
89
38
2
2
1
2
5
6
1
1
107
47
1
1
1
1
9
1
1
13
2
12
6
1
1
9
9
2
16
1
2
2
2
15
1
4
5
5
1
1
116
5
1
7
5
3
18
1
1
1
14
1
2
1
1
1
3185
1
3
3
2
1
3
7
...

result:

ok 49979 lines

Test #24:

score: 0
Accepted
time: 1388ms
memory: 10136kb

input:

50000 49999
1 2 993457878
2 3 126364173
3 4 200415238
4 5 739704607
5 6 676532686
6 7 557507714
7 8 71727068
8 9 337809709
9 10 681106495
10 11 599345798
11 12 346312387
12 13 39200895
13 14 943426213
14 15 506779546
15 16 379338416
16 17 14615880
17 18 816406736
18 19 211045210
19 20 838922528
20 2...

output:

5
9
18
53
19
1
25
4
19
1
1
1
1
1
11
1
1
2
1
9
1
13
16
5
1
2
1
1
1
7
1
1
16
1
1
5
3
2
3
3
11
2
1
1
12
1
16987
4
12
1
1
1
5
5
5
1
1
4
1
4
2
1
3
1
4
1
1
2
5
2
18
1
3
200
1
4
2
7
1
1
1
2
44
2
1
10
11
2
3
12
1
3
4
10
4
7
1
16
6
1
13
4
1
5
3
2
1
2
2
2
1
31
40
3
2
1
3
1
86
2
2
1
1
1
1
15
2
1
1
1
6
1
1
7
1
...

result:

ok 50005 lines

Test #25:

score: 0
Accepted
time: 1976ms
memory: 10056kb

input:

50000 49999
1 2 2180
2 3 39922
3 4 2857
4 5 41405
5 6 71574
6 7 34628
7 8 271216
8 9 134571
9 10 77206
10 11 98084
11 12 86039
12 13 449514
13 14 490107
14 15 450572
15 16 139688
16 17 639236
17 18 247981
18 19 75121
19 20 300881
20 21 7682
21 22 248842
22 23 599408
23 24 647942
24 25 7276
25 26 470...

output:

49496
49499
49314
30098
32346
32346
49499
30098
42345
4779
49496
42345
49314
32346
49496
49314
30098
1640
30098
30098
30098
6969
6968
40954
49314
30098
2248
30098
30098
403
40954
6969
49314
6969
30098
49498
30098
4779
40954
49499
6968
42345
30098
32346
1345
32346
49314
32346
40954
32346
6969
6969
33...

result:

ok 49911 lines

Test #26:

score: 0
Accepted
time: 1877ms
memory: 10360kb

input:

49999 49998
1 2 2541
2 3 57948
3 4 37666
4 5 66268
5 6 42284
6 7 115405
7 8 248366
8 9 262167
9 10 145846
10 11 47627
11 12 431021
12 13 218051
13 14 401077
14 15 549059
15 16 169347
16 17 363982
17 18 490171
18 19 370535
19 20 480055
20 21 327730
21 22 278018
22 23 231965
23 24 256156
24 25 329573
...

output:

450
33828
47494
47494
1249
47493
9064
9064
24764
8175
47493
8175
33828
19203
19203
3968
1811
8175
5561
1689
42003
8175
33828
42003
33828
47494
19203
5561
24764
47494
3968
16782
24764
19203
24764
47494
24764
8175
24764
47493
9064
75
9064
1689
47494
1689
1689
24764
5561
2976
33828
3968
33828
78
24764
...

result:

ok 50105 lines

Test #27:

score: 0
Accepted
time: 1818ms
memory: 10132kb

input:

49999 49998
1 2 23701
2 3 57539
3 4 70283
4 5 136271
5 6 141212
6 7 184696
7 8 228429
8 9 29895
9 10 31218
10 11 282781
11 12 29995
12 13 131524
13 14 133988
14 15 197273
15 16 351724
16 17 391575
17 18 253620
18 19 611546
19 20 216997
20 21 305541
21 22 118275
22 23 306021
23 24 482979
24 25 709132...

output:

26373
8528
1944
10472
1430
6356
3806
5934
1944
49998
8528
11437
369
363
36932
4327
3351
3351
3806
6496
1944
49973
5934
13041
19188
1857
652
2143
13254
13254
12975
49998
599
8528
1944
10472
5934
8528
19
10472
13254
10472
1935
4327
6356
11339
36932
13254
10472
4257
3806
610
6496
5934
2220
11437
1300
4...

result:

ok 50026 lines

Test #28:

score: -16
Time Limit Exceeded

input:

1 0
100000
2 1 710454586
2 1 30174257
2 1 685675008
2 1 417816804
2 1 327755609
2 1 841371333
2 1 301370841
2 1 143821498
2 1 232099091
2 1 977178764
2 1 572665966
2 1 913418066
2 1 808399404
2 1 22331931
2 1 434460344
2 1 40437984
2 1 997406768
2 1 40071081
2 1 268638772
2 1 541398526
2 1 983507437...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #33:

score: 17
Accepted
time: 876ms
memory: 9952kb

input:

32767 32766
1 2 152523690
1 3 736211233
2 4 163158345
2 5 200010458
3 6 902682843
3 7 427399287
4 8 770411775
4 9 322256303
5 10 252775416
5 11 346597970
6 12 297314023
6 13 727299741
7 14 985621564
7 15 101953231
8 16 405434218
8 17 421655547
9 18 817411034
9 19 310455840
10 20 355126049
10 21 7038...

output:

1
1
2
2
6
6
12547
1
1
1793
3
41
1
37
29734
8197
1
1
1
2
11
3
7
5
18
39
13
136
1
2
1
1
4
2
177
3
279
2
36
114
53
4
9
3
2
1
21
6
2
2
5
2
1
6
7
1
5
4
11
23129
288
196
8
1
5
9
3
1
4
45
4
1
1
5
3
3
10
18
91
1
16
829
24
1
2
8
1247
10
2
1
7
20323
8
1
2
28551
1
6
1
12
4
3
1
27
1
1
1
1
2
3
1
7
1
487
1
21
15
...

result:

ok 50019 lines

Test #34:

score: 0
Accepted
time: 352ms
memory: 8412kb

input:

8191 8190
1 2 217141764
1 3 529497259
2 4 779147272
2 5 691696039
3 6 48118037
3 7 603814603
4 8 696908741
4 9 217271102
5 10 68704258
5 11 22697519
6 12 683544026
6 13 723792342
7 14 793130995
7 15 92576446
8 16 327755609
8 17 103625834
9 18 543827967
9 19 341371333
10 20 640187172
10 21 85328878
1...

output:

3231
8191
580
3382
8191
8191
8191
8191
3212
6
4
7
6
3187
6120
6152
4
457
8191
7
2
8191
8191
8191
8191
8191
4
8191
8191
8191
8191
3605
8191
7
8191
5715
6975
8191
8191
4289
2
8191
6977
8191
2
8191
8191
4
1
1
8191
1
8191
8191
11
8191
8191
222
1
8191
5905
8191
8191
8060
8191
8191
8191
2
1
8191
8191
8191...

result:

ok 49969 lines

Test #35:

score: 0
Accepted
time: 913ms
memory: 10032kb

input:

32767 32766
1 2 217141764
1 3 529497259
2 4 762168910
2 5 862501617
3 6 287569355
3 7 60434037
4 8 741381891
4 9 846044727
5 10 559556243
5 11 841922729
6 12 260807264
6 13 108798675
7 14 165384865
7 15 803171234
8 16 680929744
8 17 534495504
9 18 618761142
9 19 633256718
10 20 244069182
10 21 40934...

output:

32767
32767
32767
32767
32767
32767
32767
32767
32767
32767
3
32767
16965
32767
2
26
32767
32767
6
1
32767
7826
32767
1
21971
7
32767
12668
5289
162
32767
15263
32767
11
32767
3
4
32767
18
118
32767
1
32767
32767
32767
5
32767
32767
39
32767
267
32767
32767
32767
32767
32767
1
7
32767
2
32767
1
228
...

result:

ok 50058 lines

Test #36:

score: 0
Accepted
time: 857ms
memory: 9012kb

input:

32767 32766
1 2 960028533
1 3 932018255
2 4 966739858
2 5 978817181
3 6 951511415
3 7 993940257
4 8 988418327
4 9 995978961
5 10 810804356
5 11 990996089
6 12 988830283
6 13 964972868
7 14 860937540
7 15 840655680
8 16 840257957
8 17 761892560
9 18 901480224
9 19 889396012
10 20 884899819
10 21 9367...

output:

5
1
6
19293
1
17937
1
1
1
1
1
3
7
1
4
6883
32026
1
1
1
2
5824
2
19
2
28839
7
1
8
12099
19229
27469
2
3
1
10692
1
21275
1
2
1
31
1
1
1
15551
1
1
1
32498
7
31105
29865
1870
31927
1
3
1
1
1
1
27524
1
9
29426
4
1
12
4
26271
1
18126
2
1
1
1
1
31028
6
8
14285
1
3103
3
2
8
2
31181
1
1
1
21314
1
7
2
1
1
244...

result:

ok 50058 lines

Test #37:

score: -17
Time Limit Exceeded

input:

1 0
100000
2 1 710454586
2 1 30174257
2 1 685675008
2 1 417816804
2 1 327755609
2 1 841371333
2 1 301370841
2 1 143821498
2 1 232099091
2 1 977178764
2 1 572665966
2 1 913418066
2 1 808399404
2 1 22331931
2 1 434460344
2 1 40437984
2 1 997406768
2 1 40071081
2 1 268638772
2 1 541398526
2 1 983507437...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #45:

score: 14
Accepted
time: 1494ms
memory: 14952kb

input:

50000 100000
35231 1616 822934828
1668 2202 768458723
26049 41810 238904165
15936 42751 466996423
41068 21425 588205829
29502 11760 732391267
13029 44741 930695124
46168 22085 155239713
9505 43779 638894800
18665 43842 298794735
41763 15511 727702105
7865 27776 53447691
32904 34081 844499614
26327 9...

output:

2
2
1
48165
37106
1
48830
1
47126
3
37777
1
14
1
1
24
1
48755
44817
17617
24322
48909
7
47708
1
41147
48949
45939
48022
1
26304
1
1
22363
24527
46076
37978
1
1
2
44508
1
47625
48554
1
2
4
48711
48431
41315
2
2
9364
3
37323
46978
39881
32373
5
39140
47126
44635
47960
1
48141
47192
28
27190
38467
4
48...

result:

ok 100000 lines

Test #46:

score: -14
Time Limit Exceeded

input:

1 0
100000
2 1 449565301
2 1 418018081
2 1 566914037
2 1 386096903
2 1 325815043
2 1 515513392
2 1 349622300
2 1 5042450
2 1 469351640
2 1 219472495
2 1 510850771
2 1 885705436
2 1 594457820
2 1 410756749
2 1 959667810
2 1 479458147
2 1 705147675
2 1 140732217
2 1 281668854
2 1 333164650
2 1 3934393...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%