QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426809#6232. 魔法森林Nevll65 1052ms520080kbC++142.3kb2024-05-31 22:03:132024-05-31 22:03:14

Judging History

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

  • [2024-05-31 22:03:14]
  • 评测
  • 测评结果:65
  • 用时:1052ms
  • 内存:520080kb
  • [2024-05-31 22:03:13]
  • 提交

answer

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
# define pii pair<int, int>
# define pll pair<ll, ll>
using namespace std;

const int sq = 317;

int par[sq + 2][100001], ukr[sq + 2][100001], idx[100001], pos[100001], val[100001];
vector< pair<pii, pii> > ss;
bool tr[100001];

int find(int a, int sz) {
	if(a == par[sz][a]) return a;
	return find(par[sz][a], sz);
}

void merge(int a, int b, int sz) {
	a = find(a, sz);
	b = find(b, sz);
	if(a == b) return;
	if(ukr[sz][a] > ukr[sz][b]) swap(a, b);
	par[sz][a] = b;
	ss.push_back({{sz, a}, {b, ukr[sz][b]}});
	ukr[sz][b] += ukr[sz][a];
	return;
}

void rollback() {
	par[ss.back().fi.fi][ss.back().fi.se] = ss.back().fi.se;
	ukr[ss.back().fi.fi][ss.back().se.fi] = ss.back().se.se;
	ss.pop_back();
}

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	
	vector< pair<pii, pii> > arr(M);
	for(int i=0;i<M;i++) {
		scanf("%d %d %d %d", &arr[i].se.fi, &arr[i].se.se, &arr[i].fi.fi, &arr[i].fi.se);
		arr[i].se.fi--;
		arr[i].se.se--;
	}
	sort(arr.begin(), arr.end());
	
	for(int i=0;i<N;i++) {
		for(int k=0;k<=sq;k++) {
			par[k][i] = par[k][i] = i;
			ukr[k][i] = 1;
		}
	}
	
	vector<pii> cpr(M);
	for(int c=0;c<M;c++) {
		cpr[c] = {arr[c].fi.se, c};
	}
	sort(cpr.begin(), cpr.end());
	for(int i=0;i<M;i++) {
		idx[cpr[i].se] = i;
		pos[i] = cpr[i].se;
		val[i] = cpr[i].fi;
	}
	
	int ans = 1e9;
	for(int i=0;i<M;i++) {
		// update status yg skrg
		tr[idx[i]] = 1;
		
		int flr = idx[i] / sq + 1;
		for(int v=flr;v<=sq + 1;v++) merge(arr[i].se.fi, arr[i].se.se, v);
		
		// skrg query
		int lf = 1, rg = sq + 1, fn = -1;
		while(lf <= rg) {
			int mid = (lf + rg) / 2;
		//	if(i == M - 1 && mid == 1) cout<<find(0, mid)<<" "<<find(N - 1, mid)<<endl;
			if(find(0, mid) == find(N - 1, mid)) {
				fn = mid;
				rg = mid - 1;
			} else lf = mid + 1;
		}
		if(fn == -1) continue;
		
	//	cout<<"mid ; "<<i<<" "<<fn<<endl;
		
		int ct = 0;
		for(int k=(fn - 1)*sq;k<fn*sq;k++) {
			if(!tr[k]) continue;
			ct++;
			merge(arr[pos[k]].se.fi, arr[pos[k]].se.se, fn - 1);
			if(find(0, fn - 1) == find(N - 1, fn - 1)) {
				ans = min(ans, arr[i].fi.fi + val[k]);
				break;
			}
		}
		while(ct--) rollback();
	}
	if(ans == 1e9) printf("-1\n");
	else printf("%d\n", ans);
	
	return 0;
}

詳細信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 253616kb

input:

5 10
2 1 9 5
5 4 9 1
5 5 8 1
4 5 10 9
5 4 7 2
4 5 7 2
2 1 1 9
2 2 10 1
5 4 7 5
3 1 7 6

output:

-1

result:

ok 1 number(s): "-1"

Test #2:

score: 5
Accepted
time: 0ms
memory: 251936kb

input:

5 10
3 4 5 10
5 2 3 8
3 3 3 7
5 4 10 2
2 1 2 3
1 1 5 6
4 1 4 2
3 4 7 2
3 3 3 3
2 2 6 9

output:

11

result:

ok 1 number(s): "11"

Test #3:

score: 5
Accepted
time: 0ms
memory: 253736kb

input:

5 10
1 2 9 7
5 1 2 2
4 4 1 3
2 4 5 8
2 1 8 10
4 1 7 1
5 4 6 2
2 1 1 3
5 5 4 6
3 1 10 1

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Wrong Answer
time: 12ms
memory: 257440kb

input:

500 3000
34 27 28594 24506
286 348 18907 30273
257 192 32208 26324
385 385 49809 27431
235 13 35303 10824
53 431 43563 13320
449 384 9996 9938
119 68 28528 11764
383 404 8115 18020
412 275 46423 12435
418 176 10786 23880
480 83 1483 4354
144 228 28970 16989
290 275 5994 24000
85 480 16829 528
29 104...

output:

23314

result:

wrong answer 1st numbers differ - expected: '20641', found: '23314'

Test #5:

score: 5
Accepted
time: 8ms
memory: 256188kb

input:

500 3000
234 418 790 17928
334 459 47327 33761
34 433 45890 43926
230 325 10888 17303
97 173 22646 17755
90 393 3226 17194
82 338 36683 15100
364 366 16732 9287
149 60 18435 9610
473 399 26471 29664
12 88 24212 12740
272 437 21962 113
215 322 3344 45385
452 151 16806 47528
101 345 21961 36434
244 34...

output:

59754

result:

ok 1 number(s): "59754"

Test #6:

score: 5
Accepted
time: 7ms
memory: 257260kb

input:

500 3000
38 162 10377 42980
482 2 41218 29435
270 258 20522 49513
236 303 15886 2699
493 232 30264 4986
285 169 11382 29404
24 38 32311 31405
38 253 41664 5143
24 86 41973 48247
437 247 15952 5937
318 417 35089 22020
132 112 46432 38269
333 297 17282 30207
100 69 10204 707
180 367 22903 987
147 417 ...

output:

70482

result:

ok 1 number(s): "70482"

Test #7:

score: 0
Wrong Answer
time: 81ms
memory: 285676kb

input:

5000 10000
4100 2417 16875 26776
4528 853 11398 32026
4385 2640 2392 4454
3279 2885 613 3173
2114 1792 1216 477
4882 3093 296 559
3899 3160 13550 4902
1639 4471 2638 1790
4875 2143 11367 15078
2528 2100 799 1353
4887 2385 407 2867
4052 2944 48666 23634
2864 2050 8712 29348
2663 203 4189 1578
2983 31...

output:

14637

result:

wrong answer 1st numbers differ - expected: '8863', found: '14637'

Test #8:

score: 5
Accepted
time: 86ms
memory: 285856kb

input:

5000 10000
1401 4578 41261 49838
2688 3887 2101 33977
1695 3634 32413 46614
345 41 2173 36590
1790 1702 14869 6635
3655 4213 5093 37235
3347 3374 27529 7106
1465 4978 38619 14626
1743 2922 31985 14161
4602 3268 31256 39384
60 3172 24903 12181
914 2185 46314 29478
1205 616 28881 396
4196 2851 14719 4...

output:

78312

result:

ok 1 number(s): "78312"

Test #9:

score: 5
Accepted
time: 76ms
memory: 285028kb

input:

5000 10000
2656 3982 6846 1999
632 3583 1790 9561
3349 824 7095 10058
883 763 1220 10463
79 1402 1128 284
4277 4305 176 829
2524 3803 42715 15180
1308 3123 13633 34650
3141 1285 8989 6216
2498 3710 7295 5857
4343 4728 7689 27158
1025 114 2836 7594
3970 1533 45449 15420
1541 816 47142 37127
2732 384 ...

output:

22373

result:

ok 1 number(s): "22373"

Test #10:

score: 5
Accepted
time: 75ms
memory: 284512kb

input:

5000 10000
2156 1635 29203 20144
524 3709 37325 41470
4544 3373 27716 26147
2419 585 35320 9459
4197 1738 21633 1250
2473 2913 8315 33285
1060 3111 17595 10861
4162 657 4379 19458
3292 4047 12330 24303
1260 3475 5967 22531
1516 3748 12635 38081
594 4008 35283 31958
2929 4216 4941 8714
526 3893 27129...

output:

76197

result:

ok 1 number(s): "76197"

Test #11:

score: 0
Wrong Answer
time: 1004ms
memory: 518160kb

input:

50000 100000
35738 22002 17 23366
33128 44965 3 20356
33714 6605 26 36170
45098 2222 19 21638
34364 39859 28 45303
40193 35296 22 36797
38375 26797 20 41156
33242 21039 30 19453
31843 49130 29 5994
28968 4578 15 48411
16291 30818 28 40446
30977 47872 9 49339
47005 35013 27 40634
10430 6544 25 8509
4...

output:

14166

result:

wrong answer 1st numbers differ - expected: '13916', found: '14166'

Test #12:

score: 5
Accepted
time: 1008ms
memory: 518036kb

input:

50000 100000
40013 32726 13 42954
32155 23252 12 22022
46394 42849 10 10587
31419 34736 15 28602
26813 27188 1 544
37584 26975 26 49570
47510 43458 14 19080
38654 48446 12 37829
45059 29549 27 46424
48992 2102 28 8873
30209 4160 10 24434
28346 18493 24 19716
19763 24073 7 25394
22176 7405 15 49611
2...

output:

15901

result:

ok 1 number(s): "15901"

Test #13:

score: 0
Wrong Answer
time: 1015ms
memory: 517412kb

input:

50000 100000
16842 45534 10 46814
25441 26842 6 39489
12615 34736 26 4723
30099 11317 20 16904
15696 29980 9 18655
28179 41056 7 46122
16220 7076 21 43462
20238 47722 9 31185
3143 21323 29 47018
20774 31264 19 35573
4768 9775 2 3664
13440 43681 30 19444
31763 41464 12 5177
16337 33573 18 11358
34525...

output:

22148

result:

wrong answer 1st numbers differ - expected: '20762', found: '22148'

Test #14:

score: 0
Wrong Answer
time: 986ms
memory: 518864kb

input:

50000 100000
23345 48443 12 16531
30387 14890 30 44747
49397 43020 3 19321
49081 37787 5 34097
39128 22545 23 7618
6537 8023 17 29209
33146 23346 4 46496
27760 268 11 10328
18203 19926 16 32081
39042 11301 7 4009
46246 33981 4 43144
6046 25773 18 47084
24100 20456 13 36246
23265 33510 21 39038
18153...

output:

25383

result:

wrong answer 1st numbers differ - expected: '25382', found: '25383'

Test #15:

score: 5
Accepted
time: 1021ms
memory: 519372kb

input:

50000 100000
20059 12595 28734 37114
9174 46509 14959 49621
4767 36912 47857 33474
2399 39934 48056 19734
25960 40619 27470 37588
16019 43158 1088 6663
19377 23301 35682 32888
38957 43679 9009 4194
45878 49053 41268 6315
38491 40864 35788 14218
36120 37388 4145 13635
40859 14433 32488 23226
33385 41...

output:

28263

result:

ok 1 number(s): "28263"

Test #16:

score: 5
Accepted
time: 1015ms
memory: 517944kb

input:

50000 100000
20085 3392 42620 38601
4309 46769 1871 3724
2870 8853 2763 5734
7793 30588 4733 1237
46002 5479 11930 12405
36083 22319 23019 9692
42724 5862 5326 814
8575 4116 6412 5930
38001 6994 15664 26152
34015 8868 11361 37491
37121 27584 43656 21169
15673 13442 4674 6186
40197 18033 31926 27791
...

output:

12661

result:

ok 1 number(s): "12661"

Test #17:

score: 5
Accepted
time: 1052ms
memory: 520080kb

input:

50000 100000
12593 8853 15846 20005
7883 13508 9118 2406
27550 36107 24528 6533
43521 33321 14399 15371
37857 45745 10915 10972
23848 1562 9890 39500
47198 19163 33992 36561
17290 17439 14282 5305
32899 42874 12118 41495
27576 29894 4410 8194
21906 43433 40276 19560
9376 4885 31039 1491
4085 16754 4...

output:

29990

result:

ok 1 number(s): "29990"

Test #18:

score: 0
Wrong Answer
time: 989ms
memory: 517712kb

input:

50000 100000
13022 28302 15006 24082
14360 31098 16233 46751
31593 17522 43605 8880
24445 8663 2130 3167
12824 14750 40933 16954
32504 16604 1522 1969
23019 47172 35428 49655
40944 13925 2683 1143
5481 17764 44731 45569
46062 33741 42476 5617
22675 11519 2655 14517
10282 14585 34306 22609
14565 2069...

output:

18168

result:

wrong answer 1st numbers differ - expected: '6381', found: '18168'

Test #19:

score: 0
Wrong Answer
time: 988ms
memory: 518592kb

input:

50000 100000
32164 31566 40831 5088
39808 1214 10742 32333
41688 41818 458 1378
4215 28911 16083 27983
33506 11546 49059 14306
7272 12695 3644 8786
20956 36799 8762 2460
24555 43357 27955 1532
21045 22681 41806 44841
33519 7431 34302 46163
4750 24033 39819 1620
33028 2343 44285 35008
18438 28155 251...

output:

24596

result:

wrong answer 1st numbers differ - expected: '18006', found: '24596'

Test #20:

score: 5
Accepted
time: 1019ms
memory: 518916kb

input:

50000 100000
3621 21738 6817 6604
35031 36302 11064 36482
29740 32541 23043 20537
10982 952 8683 6349
29645 4942 1146 1632
1505 37196 43636 6749
3458 18776 301 16002
8377 29669 4106 593
5171 16708 30184 10903
14967 35348 46677 21683
37351 8284 38743 42527
26265 22278 41608 21536
19781 17366 5707 834...

output:

20256

result:

ok 1 number(s): "20256"