QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#274574#7883. Takeout Delivering_whb#WA 243ms51376kbC++202.0kb2023-12-03 17:49:262023-12-03 17:49:27

Judging History

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

  • [2023-12-03 17:49:27]
  • 评测
  • 测评结果:WA
  • 用时:243ms
  • 内存:51376kb
  • [2023-12-03 17:49:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std ;
const int N = 3e5 + 5, M = 1e6 + 5 ;
using ll = long long ;

int n, m ;
int fa[N] ;
int L[M], R[M], w[M] ;
int id[M], val[N], val2[N] ;

int get(int x) { return x == fa[x] ? x : x = fa[x] = get(fa[x]) ; }

void merge(int x, int y)
{
	int l = get(x), r = get(y) ;
	if(l != r) fa[r] = l ;
}

bool isMerge(int x, int y)
{
	int l = get(x), r = get(y) ;
	return l == r ;
}

vector<pair<int, int>> g[N] ;

int pre[N], go[N] ;
bool in[M] ;

void dfs(int x, int f)
{
	for(auto [y, z] : g[x]) if(y != f)
	{
		pre[y] = z ; go[y] = x ;
		val[y] = max(val[x], z) ;
		dfs(y, x) ;
	}
}

void dfs2(int x, int f)
{
	for(auto [y, z] : g[x]) if(y != f)
	{
		val2[y] = max(val2[x], z) ;
		dfs2(y, x) ;
	}
}

int main()
{
	ios::sync_with_stdio(false) ;
	cin.tie(nullptr) ;
	
	cin >> n >> m ;
	for(int i = 1; i <= m; ++ i)
	{
		cin >> L[i] >> R[i] >> w[i] ;
		id[i] = i ;
	}

	stable_sort(id + 1, id + m + 1, [&](int x, int y) {
		return w[x] < w[y] ;
	}) ;

	if(m == 1) return cout << w[1] << '\n', 0 ;
	
	for(int i = 1; i <= n; ++ i) fa[i] = i ;

	int maxz = 0 ;
	for(int i = 1; i <= m; ++ i)
	{
		int x = L[id[i]], y = R[id[i]], z = w[id[i]] ;

		if(!isMerge(x, y))
		{
			merge(x, y) ;
			in[id[i]] = 1 ;
			g[x].push_back({y, z}) ;
			g[y].push_back({x, z}) ;
			maxz = z ;
		}
 	}

 	dfs(1, 0) ;
 	dfs2(n, 0) ;

 	vector<int> dist ;
 	int pos = n ;
 	while(pos != 1) dist.push_back(pre[pos]), pos = go[pos] ;

 	sort(dist.begin(), dist.end(), greater<int>()) ; 

 	ll ans = INT_MAX ;

 	if((int)dist.size() == 1) ans = dist[0] ;
 	else ans = dist[0] + dist[1] ;

 	// for(int i = 1; i <= m; ++ i) cout << in[id[i]] << " \n"[i == m] ;

 	for(int i = 1; i <= m; ++ i) if(w[id[i]] >= maxz)
 	{
 		// if(in[id[i]]) continue ;
 		// cout << "KK" << '\n' ;
 		int x = L[id[i]], y = R[id[i]], z = w[id[i]] ;
 		ans = min(ans, max(val[x], val2[y]) + (ll)z) ;
 		ans = min(ans, max(val2[x], val[y]) + (ll)z) ;
 	}

 	cout << ans << '\n' ;
	return 0 ;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 24120kb

input:

4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

output:

5

result:

ok 1 number(s): "5"

Test #2:

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

input:

300000 299999
80516 80517 597830404
110190 110191 82173886
218008 218009 954561262
250110 250111 942489774
66540 66541 156425292
34947 34948 239499776
273789 273790 453201232
84428 84429 439418398
98599 98600 326095035
55636 55637 355015760
158611 158612 684292473
43331 43332 43265001
171621 171622 ...

output:

1999991697

result:

ok 1 number(s): "1999991697"

Test #3:

score: 0
Accepted
time: 243ms
memory: 43796kb

input:

300000 299999
207226 231742 414945003
84591 210444 175968953
46327 51582 612565723
18773 141119 82562646
76139 286963 762958587
131867 224820 928900783
215240 216181 405340417
144725 290878 195350550
267216 268752 846015171
31413 255927 389339642
45219 147512 489502910
113391 215402 555706684
53359 ...

output:

1989898633

result:

ok 1 number(s): "1989898633"

Test #4:

score: 0
Accepted
time: 123ms
memory: 44448kb

input:

300000 299999
1 118488 989720257
1 181002 810258689
1 254222 172925351
1 176703 737330574
1 218306 941887568
1 105741 645573853
1 188490 794789787
1 273997 91455946
1 214929 293300204
1 127289 600097406
1 30589 330284120
1 128954 532459734
1 163729 627033607
1 24073 718818252
1 41571 755054850
1 560...

output:

725564985

result:

ok 1 number(s): "725564985"

Test #5:

score: 0
Accepted
time: 186ms
memory: 49784kb

input:

300000 299999
19784 19785 438457172
153297 239456 192671538
153297 202254 645947104
9640 9641 583410541
153297 221084 490232940
32210 32211 838809517
153297 171896 625627853
153297 216946 683286844
110843 110844 690710575
153297 176413 983037656
74908 74909 375017711
67676 67677 695121437
153297 196...

output:

1999992880

result:

ok 1 number(s): "1999992880"

Test #6:

score: 0
Accepted
time: 229ms
memory: 51376kb

input:

300000 299999
130662 244000 579178004
167657 294630 753914681
61924 61925 165841675
113560 113561 979316325
151574 218075 973289843
1224 1225 230803236
133441 133442 806726301
167309 249456 853031541
120245 120246 688705252
142688 217826 692299631
106114 106115 735998084
123268 123269 749737073
1208...

output:

1999989691

result:

ok 1 number(s): "1999989691"

Test #7:

score: 0
Accepted
time: 175ms
memory: 37000kb

input:

300000 299999
54474 108948 971770803
11077 22155 470962125
115359 230718 373029049
124472 248944 865510218
11958 23917 100575860
130349 260698 582886291
17563 35127 697131917
54427 108854 274252758
51546 103092 198620066
100126 200252 154524070
14994 29988 528701437
147502 295004 531813162
42285 845...

output:

1823402145

result:

ok 1 number(s): "1823402145"

Test #8:

score: 0
Accepted
time: 197ms
memory: 45008kb

input:

300000 299999
240182 240189 427579190
41871 41880 360542232
57131 57140 353813367
122650 122653 621913649
67332 67340 271427538
107523 107524 774306311
60374 60379 315636931
130805 130808 667109508
154531 154534 327293148
138561 138569 833879694
32543 32551 382610722
287398 287400 211744079
59693 59...

output:

1999983202

result:

ok 1 number(s): "1999983202"

Test #9:

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

input:

10 20
1 6 98
3 4 3
4 5 26
7 8 72
1 2 86
3 7 83
7 10 89
4 7 100
3 6 59
6 9 74
5 6 28
6 7 1
2 9 100
2 6 99
5 10 85
8 10 97
2 10 98
8 9 3
2 3 94
9 10 71

output:

170

result:

ok 1 number(s): "170"

Test #10:

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

input:

10 20
2 8 94
3 7 81
8 10 85
2 4 88
4 5 90
1 4 96
3 6 95
7 10 77
1 8 98
4 7 91
2 6 38
1 10 89
1 3 45
4 9 94
3 9 64
6 10 83
5 8 19
2 5 81
6 7 92
3 4 92

output:

89

result:

ok 1 number(s): "89"

Test #11:

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

input:

10 20
1 6 58
1 4 80
1 10 28
1 3 46
6 7 76
7 10 75
4 9 95
2 10 92
1 7 15
9 10 52
3 6 93
5 7 94
1 2 75
1 5 41
3 7 79
4 8 94
2 6 80
6 9 63
1 9 42
1 8 9

output:

28

result:

ok 1 number(s): "28"

Test #12:

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

input:

10 20
6 9 79
5 6 72
2 5 74
2 4 74
8 10 90
1 5 82
3 4 55
6 10 94
7 8 55
3 7 92
1 8 83
9 10 93
4 7 98
4 5 24
2 3 28
6 7 24
1 2 63
3 10 99
8 9 2
5 10 95

output:

158

result:

ok 1 number(s): "158"

Test #13:

score: -100
Wrong Answer
time: 5ms
memory: 22056kb

input:

10 20
3 4 75
5 7 98
3 10 91
5 8 41
2 7 84
2 3 73
4 10 100
2 4 80
1 5 99
3 9 79
4 5 97
4 9 10
4 7 52
1 10 96
8 10 98
6 9 99
1 2 50
5 9 98
2 9 93
3 6 92

output:

164

result:

wrong answer 1st numbers differ - expected: '96', found: '164'