QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291073#4155. 消防MoRanSky100 ✓180ms21284kbC++142.3kb2023-12-26 04:45:102023-12-26 04:45:10

Judging History

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

  • [2023-12-26 04:45:10]
  • 评测
  • 测评结果:100
  • 用时:180ms
  • 内存:21284kb
  • [2023-12-26 04:45:10]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <limits.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 500001;
int n, ss, dis[N], pre[N], q[N]; 
int head[N], numE = 0;
bool vis[N];
vector<PII> path; 
struct Edge{
    int next, to, dis;
}e[N << 1];
void addEdge(int from, int to, int dis){
    e[++numE].next = head[from];
    e[numE].to = to;
    e[numE].dis = dis;
    head[from] = numE;
}
int inline bfs(int s){
	memset(vis, false, sizeof vis);
	dis[s] = 0; vis[s] = true;
	pre[s] = 0;
	q[0] = s;
    int hh = 0, tt = 0;
	while(hh <= tt){
		int u = q[hh++];
		for(register int i = head[u]; i; i = e[i].next){
			int v = e[i].to;
			if(vis[v]) continue;
			vis[v] = true;
			dis[v] = dis[u] + e[i].dis;
			pre[v] = u;
            q[++tt] = v;
		}
	}
	int k, maxn = -1;
	for(int i = 1; i <= n; i++)
		if(dis[i] > maxn) maxn = dis[i], k = i;
	return k;
}

int inline bfs2(int s){
	int hh = 0, tt = 0, res = 0;
	q[0] = s;
	while(hh <= tt){
		int u = q[hh++];
        res = max(res, dis[u]);
		for(register int i = head[u]; i; i = e[i].next){
			int v = e[i].to;
			if(vis[v]) continue;
			vis[v] = true;
			dis[v] = dis[u] + e[i].dis;
			q[++tt] = v;
		}
	}
	return res;
}
bool check(int m){
	memset(vis, false, sizeof vis);
	memset(dis, 0, sizeof dis);
	int u = 0, v = path.size() - 1;
	while(u + 1 < path.size() && path[u + 1].second <= m) u++;
	while(v && path[path.size() - 1].second - path[v - 1].second <= m) v--;
    if(u > v) return true;
	if(path[v].second - path[u].second > ss) return false;
	

    for(int i = 0; i < path.size(); i++)
        vis[path[i].first] = true;
    for(int i = u; i <= v; i++)
		if(bfs2(path[i].first) > m) return false;
	
	return true; 
}
int main(){
	scanf("%d%d", &n, &ss);
	for(register int i = 1; i < n; i++){
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		addEdge(u, v, w);
        addEdge(v, u, w);
	}
	int u = bfs(1), v = bfs(u);
	
	while(v != 0){
		path.push_back(make_pair(v, dis[v]));
		v = pre[v];
	}
	
	reverse(path.begin(), path.end());
	
	int l = 0, r = INT_MAX;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}

詳細信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 13728kb

input:

300 45969
250 205 200
183 152 520
137 266 462
185 18 318
90 228 200
228 4 346
294 264 645
130 7 986
46 252 97
56 281 404
289 68 382
218 41 277
28 74 453
4 96 99
30 231 692
1 214 935
286 273 944
244 28 738
117 83 245
176 208 173
184 258 898
121 124 760
143 176 68
65 199 279
13 222 924
88 67 31
200 9 ...

output:

6719

result:

ok single line: '6719'

Test #2:

score: 10
Accepted
time: 0ms
memory: 12828kb

input:

300 42475
76 206 113
197 33 585
258 132 82
27 4 992
112 113 658
22 40 560
35 68 351
25 42 313
143 191 54
121 140 86
174 101 889
98 159 398
279 70 668
126 189 953
241 97 566
268 48 792
264 196 990
230 54 609
22 166 228
83 257 719
273 183 835
142 221 219
129 198 893
273 75 704
160 19 827
245 27 180
27...

output:

6282

result:

ok single line: '6282'

Test #3:

score: 10
Accepted
time: 0ms
memory: 13064kb

input:

300 22760
163 181 233
299 238 105
42 233 910
245 238 386
65 245 158
14 163 83
195 137 559
98 164 820
79 241 905
61 250 212
87 160 973
147 138 546
29 278 138
102 294 886
92 137 493
286 210 100
280 79 491
197 294 465
278 152 601
122 104 54
114 222 571
288 60 396
202 217 496
265 220 26
137 293 663
102 ...

output:

6498

result:

ok single line: '6498'

Test #4:

score: 10
Accepted
time: 0ms
memory: 12604kb

input:

3000 94392
538 1961 290
1948 572 902
304 1085 744
1277 2279 817
756 1411 559
120 1449 761
74 1940 129
2862 1440 487
2473 646 23
88 1919 846
1353 2043 88
1762 1069 534
1494 2492 621
324 1443 66
1592 1466 661
1269 2525 927
2569 1482 506
115 1017 69
1506 1628 654
924 2849 73
2781 676 367
1000 853 240
1...

output:

18919

result:

ok single line: '18919'

Test #5:

score: 10
Accepted
time: 5ms
memory: 12292kb

input:

3000 570732
521 2760 207
2094 2711 896
634 1466 433
1669 1790 626
210 716 737
2543 989 711
1715 885 873
2641 817 695
2521 1438 30
1236 1580 410
947 1636 498
1167 1255 463
515 1886 533
28 884 203
1637 2630 763
1007 954 879
2213 429 60
1627 727 925
274 215 310
2466 1255 989
2274 1574 441
1371 2535 458...

output:

22537

result:

ok single line: '22537'

Test #6:

score: 10
Accepted
time: 158ms
memory: 21084kb

input:

300000 29425391
37345 284991 980
68049 178671 807
170719 106976 508
141657 98784 539
181242 73981 304
71837 36585 70
298192 119962 644
215378 114873 686
221421 294307 609
243110 272615 838
278109 973 463
185175 103375 895
148501 240531 256
28238 276708 904
169368 108166 161
217632 157881 583
94405 2...

output:

104555

result:

ok single line: '104555'

Test #7:

score: 10
Accepted
time: 161ms
memory: 19828kb

input:

300000 8534504
18907 268396 647
118029 206413 279
148395 242275 695
88202 289413 793
202819 258264 85
10231 7416 929
165705 166308 106
151635 14294 448
51126 117396 514
178876 48461 704
227076 164145 331
86560 149150 604
234104 184732 874
163391 193056 739
92340 208802 400
39782 206550 827
25519 210...

output:

106552

result:

ok single line: '106552'

Test #8:

score: 10
Accepted
time: 180ms
memory: 21284kb

input:

300000 24025076
152409 60121 527
12145 206872 792
186536 218998 513
211087 195910 695
258480 236228 964
11114 275727 157
137761 263314 292
30962 204377 749
45574 160894 570
77696 126052 668
48930 163850 0
14395 288377 917
14979 141714 819
292147 283008 692
38072 140117 568
97677 240283 401
207011 27...

output:

90509

result:

ok single line: '90509'

Test #9:

score: 10
Accepted
time: 152ms
memory: 21044kb

input:

300000 49267210
7745 275362 141
159354 106212 17
106319 277958 238
265761 90119 721
208150 45572 627
92881 48396 40
252802 89923 839
273475 59281 405
65423 168870 381
112599 79462 118
145257 73621 177
253269 63581 209
220158 1071 774
155833 264705 412
285389 268861 192
264788 61672 886
106359 53016 ...

output:

121725

result:

ok single line: '121725'

Test #10:

score: 10
Accepted
time: 124ms
memory: 21176kb

input:

300000 9148447
88300 243251 185
57787 64833 361
243147 274052 977
297701 229255 757
173366 4142 767
39514 150952 39
281642 155716 898
2418 126144 116
235365 170377 115
172728 171435 909
247514 268600 55
166481 173020 971
45607 79323 156
63844 60215 712
97605 14950 585
198623 265859 908
230643 16981 ...

output:

113400

result:

ok single line: '113400'