QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#426809 | #6232. 魔法森林 | Nevll | 65 | 1052ms | 520080kb | C++14 | 2.3kb | 2024-05-31 22:03:13 | 2024-05-31 22:03:14 |
Judging History
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"