QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291073 | #4155. 消防 | MoRanSky | 100 ✓ | 180ms | 21284kb | C++14 | 2.3kb | 2023-12-26 04:45:10 | 2023-12-26 04:45:10 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'