QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864480 | #4272. Phone Plans | lfxxx | 0 | 438ms | 144872kb | C++14 | 3.2kb | 2025-01-20 17:18:49 | 2025-01-20 17:18:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
#define int ll
constexpr int N = 6e5 + 5, inf = 1e9 + 9;
int n, a, b, cnt, fa[N], siz[N], in[N], tot;
ll k, sum;
unordered_map<int, int>mp[N];
vector<int>v[N];
set<int>e[N];
struct edge {
int u, v, w;
}e1[N], e2[N], tmp[N];
int find(int k)
{
return fa[k] == k ? k : fa[k] = find(fa[k]);
}
ll h(int n)
{
return (ll) n * (n - 1) / 2;
}
ll work(edge *e, int &m)
{
cnt = 0;
for (int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
sort(e + 1, e + 1 + m, [](edge a, edge b) {
return a.w < b.w;
});
for (int i = 1; i <= m; ++i) {
int fx = find(e[i].u), fy = find(e[i].v);
if (fx != fy) {
fa[fx] = fy;
siz[fy] += siz[fx];
tmp[++cnt] = e[i];
}
}
m = cnt;
copy(tmp + 1, tmp + 1 + m, e + 1);
e[m + 1] = {0, 0, 0};
ll ans = 0;
for (int i = 1; i <= n; ++i) {
if (find(i) == i) {
ans += h(siz[i]);
}
}
return ans;
}
int dfs(int u, int f, int c)
{
if (in[u]) {
sum += h(mp[find(u)][in[u]]) + h(mp[find(u)][c]);
--mp[find(u)][in[u]];
++mp[find(u)][c];
sum -= h(mp[find(u)][in[u]]) + h(mp[find(u)][c]);
} else {
++mp[find(u)][c];
}
in[u] = c;
int ans = 1;
for (int v : e[u]) {
if (v != f) {
ans += dfs(v, u, c);
}
}
return ans;
}
bool en;
signed main()
{
#ifdef IAKIOI
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n----------------------------" << endl;
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b >> k;
for (int i = 1; i <= a; ++i) {
cin >> e1[i].u >> e1[i].v >> e1[i].w;
}
for (int i = 1; i <= b; ++i) {
cin >> e2[i].u >> e2[i].v >> e2[i].w;
}
work(e1, a);
sum = work(e2, b);
sort(e2 + 1, e2 + 1 + b, [](edge a, edge b) {
return a.w > b.w;
});
for (int i = 1; i <= b; ++i) {
e[e2[i].u].emplace(e2[i].v);
e[e2[i].v].emplace(e2[i].u);
}
for (int i = 1; i <= n; ++i) {
fa[i] = i, siz[i] = 1;
v[i].emplace_back(i);
}
for (int i = 1; i <= n; ++i) {
if (!in[i]) {
dfs(i, 0, ++tot);
}
}
int ans = inf;
for (int i = 0, j = 1; ; ++i) {
while (sum >= k) {
// cerr << i << ' ' << j << ' ' << e1[i].w << ' ' << e2[j].w << ' ' << sum << '\n';
ans = min(ans, e1[i].w + e2[j].w);
if (j > b) break;
int u = e2[j].u, v = e2[j].v;
int szx = dfs(u, v, ++tot);
int szy = dfs(v, u, ++tot);
sum -= h(szx + szy);
sum += h(szx) + h(szy);
++j;
e[u].erase(v);
e[v].erase(u);
// cerr << i << ' ' << j << ' ' << e1[i].w << ' ' << e2[j].w << ' ' << sum << '\n';
}
if (i == a) break;
int fx = find(e1[i + 1].u), fy = find(e1[i + 1].v);
if (siz[fx] > siz[fy]) swap(fx, fy);
fa[fx] = fy;
sum -= h(siz[fx]) + h(siz[fy]);
siz[fy] += siz[fx];
sum += h(siz[fy]);
for (int x : v[fx]) {
v[fy].emplace_back(x);
sum += h(mp[fx][in[x]]) + h(mp[fy][in[x]]);
--mp[fx][in[x]];
++mp[fy][in[x]];
sum -= h(mp[fx][in[x]]) + h(mp[fy][in[x]]);
}
unordered_map<int, int>_;
mp[fx].swap(_);
}
cout << (ans == inf ? -1 : ans) << endl;
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 12ms
memory: 89696kb
input:
6 4 4 9 1 2 1 2 3 2 1 4 3 3 4 4 5 6 40 1 5 30 2 6 20 3 6 10
output:
33
result:
ok single line: '33'
Test #2:
score: 6
Accepted
time: 6ms
memory: 87780kb
input:
1 0 0 0
output:
0
result:
ok single line: '0'
Test #3:
score: 6
Accepted
time: 10ms
memory: 89628kb
input:
2 0 0 1
output:
-1
result:
ok single line: '-1'
Test #4:
score: 6
Accepted
time: 10ms
memory: 89832kb
input:
2 10 10 1 1 1 915886339 2 2 430624192 1 1 879808770 1 2 577221915 1 1 439429731 1 2 304911826 1 1 148009333 1 2 51122687 1 1 558282772 1 2 421196385 2 1 436692145 1 2 654020563 2 2 162573477 2 2 989531779 1 1 646687051 2 2 549037477 2 2 699532275 1 1 679375858 2 1 83352965 2 1 415698228
output:
51122687
result:
ok single line: '51122687'
Test #5:
score: 6
Accepted
time: 12ms
memory: 89700kb
input:
2 10 10 1 1 1 1000000000 1 2 1000000000 2 2 1000000000 2 1 1000000000 1 2 1000000000 1 1 1000000000 1 2 1000000000 2 2 1000000000 1 2 1000000000 1 2 1000000000 2 1 1000000000 1 2 1000000000 2 1 1000000000 2 2 1000000000 1 2 1000000000 2 2 1000000000 1 1 1000000000 1 1 1000000000 2 2 1000000000 1 2 1...
output:
1000000000
result:
ok single line: '1000000000'
Test #6:
score: 6
Accepted
time: 197ms
memory: 119784kb
input:
2000 0 200000 1199833 636 1231 120395621 689 1640 497332138 1861 1980 798839749 560 1283 560726905 1332 328 431171189 1203 1764 466367210 1102 347 317109768 1462 789 761470540 350 1093 551905741 1718 1047 548650524 51 546 56733461 58 1519 744207013 826 956 943929583 1969 207 238061756 99 47 99683567...
output:
9768257
result:
ok single line: '9768257'
Test #7:
score: 6
Accepted
time: 52ms
memory: 94228kb
input:
2000 200000 0 1937051 1325 1770 628367155 105 1670 728177982 358 778 959944062 826 1691 651665248 1119 1906 382208628 1684 1232 677646622 807 265 902880211 1685 1660 405567549 1853 1982 988679307 1241 1054 385406922 862 1049 356441384 1837 673 443580113 1082 1795 738355567 1703 663 221254144 1792 84...
output:
20263921
result:
ok single line: '20263921'
Test #8:
score: 6
Accepted
time: 192ms
memory: 96744kb
input:
2000 200000 200000 1999000 1303 1065 135024256 1400 1409 157921645 1208 515 422761224 466 1398 267944161 40 1202 560552418 722 1817 773826339 1022 1534 720452215 1512 200 145291518 538 230 98848391 434 529 911575234 470 1050 103133355 1800 351 180303134 1527 1871 779519820 258 1872 279904732 1 512 4...
output:
1999
result:
ok single line: '1999'
Test #9:
score: 6
Accepted
time: 198ms
memory: 98668kb
input:
2000 200000 200000 1999000 1566 1720 828051227 411 209 634755980 293 258 80524979 1149 1694 253684780 71 597 899974207 1934 440 11614281 1846 870 794303074 800 1090 576722282 1022 1619 486756658 1135 1004 589873220 1300 326 565865513 114 341 308227260 310 134 735603010 437 291 714079414 930 1131 136...
output:
1999
result:
ok single line: '1999'
Test #10:
score: 6
Accepted
time: 196ms
memory: 102636kb
input:
2000 200000 200000 1999000 1505 1008 194848918 955 1466 251380587 306 119 329528655 1072 1067 684468438 1798 755 822161204 1475 1987 886864916 609 790 525637795 1937 1639 534864650 63 792 948290690 1282 553 998185081 1995 243 367638087 1517 982 238895274 1891 358 612397768 229 1599 453255817 200 115...
output:
1999
result:
ok single line: '1999'
Test #11:
score: 6
Accepted
time: 191ms
memory: 96616kb
input:
2000 200000 200000 1999000 888 998 519088944 896 217 366603047 963 1703 281897731 1419 1583 296352197 318 1644 449932680 1252 683 299241251 1763 1736 16908823 400 673 940814267 1864 1654 16539370 21 1360 526031095 320 1052 879613936 383 555 433309121 243 869 603865861 567 236 829646077 1057 1138 545...
output:
2000
result:
ok single line: '2000'
Test #12:
score: 6
Accepted
time: 9ms
memory: 88036kb
input:
2000 0 0 0
output:
0
result:
ok single line: '0'
Test #13:
score: 6
Accepted
time: 11ms
memory: 90088kb
input:
2000 0 0 1
output:
-1
result:
ok single line: '-1'
Test #14:
score: 6
Accepted
time: 10ms
memory: 88032kb
input:
2000 0 0 1999000
output:
-1
result:
ok single line: '-1'
Test #15:
score: 6
Accepted
time: 438ms
memory: 144232kb
input:
2000 200000 200000 0 584 721 144517612 1593 1184 19655376 572 91 267489352 441 830 206284803 326 901 399207297 1220 164 270714861 1760 1765 242123575 1341 1187 778391819 247 104 618482901 1650 876 469853007 1338 660 237312298 593 1856 254405769 477 1212 387844191 603 1896 336160240 1397 444 77343103...
output:
0
result:
ok single line: '0'
Test #16:
score: 6
Accepted
time: 362ms
memory: 138724kb
input:
2000 200000 200000 1 1961 656 558726882 677 479 191436128 1411 291 100142168 932 1506 28223846 1264 1394 780504516 1276 1479 56569386 1363 65 480245792 1598 78 760054359 78 36 593906829 1112 535 999996793 1792 953 155333434 149 239 901391869 791 1800 803139774 1856 629 626568419 1931 779 330675974 8...
output:
2823
result:
ok single line: '2823'
Test #17:
score: 6
Accepted
time: 368ms
memory: 143084kb
input:
2000 200000 200000 4 1165 1872 797718594 1169 1055 624587802 866 899 658187098 1376 1679 853872729 635 1186 401602136 1058 241 170579264 1988 1953 539060919 1695 772 816154776 1551 1453 798051114 1678 810 856500252 637 1519 373040351 1663 1237 499974912 1222 174 950339946 952 1956 666630512 1053 17 ...
output:
13422
result:
ok single line: '13422'
Test #18:
score: 6
Accepted
time: 394ms
memory: 143212kb
input:
2000 200000 200000 51 825 28 972433150 472 1380 981558124 178 1129 462887818 496 1916 874585551 1806 1093 459363528 853 1063 835229701 1473 1816 509538236 1762 139 445678501 600 826 116492230 1924 1426 768569961 1093 802 138198370 1285 101 612512942 1696 527 863059072 1729 1091 238488099 1799 1725 9...
output:
207785
result:
ok single line: '207785'
Test #19:
score: 6
Accepted
time: 367ms
memory: 139320kb
input:
2000 200000 200000 346 479 1073 12925746 1739 528 708374552 1669 1597 187841053 420 1886 665883774 264 1753 39508213 1618 1695 153537785 734 950 163927318 946 639 332538805 1151 821 988862824 981 1265 633217016 1627 199 830812032 116 579 44204899 511 403 764449881 1828 538 469036862 953 1145 6928974...
output:
1325200
result:
ok single line: '1325200'
Test #20:
score: 6
Accepted
time: 394ms
memory: 139752kb
input:
2000 200000 200000 7700 1618 867 271795108 1951 151 702948614 463 231 446592273 882 479 999691562 1160 1496 458774157 862 177 365391789 1483 1529 152692222 1086 1926 981642023 650 1846 36577190 1541 1521 287755177 1549 145 326097587 1355 1965 846861888 968 1069 919410456 557 6 666217744 499 1453 429...
output:
4833174
result:
ok single line: '4833174'
Test #21:
score: 6
Accepted
time: 396ms
memory: 139752kb
input:
2000 200000 200000 10274 427 1831 50634939 924 761 973624360 1716 77 896823723 1770 286 368244715 281 1652 693233017 782 982 856834549 1990 872 586803005 1104 545 550493462 438 75 19630828 1939 95 811185364 1691 325 517180701 1832 1560 781228281 687 1611 15723447 651 73 423147727 1750 768 923943157 ...
output:
4715135
result:
ok single line: '4715135'
Test #22:
score: 6
Accepted
time: 389ms
memory: 137320kb
input:
2000 200000 200000 353724 828 1686 612966370 1332 36 325102273 50 1233 839762664 1389 740 256158152 640 18 76640380 1324 508 966364428 1791 314 236880043 1092 1586 81535148 602 1178 352534909 640 1224 733613612 970 297 526950089 1654 1677 277859934 1583 1933 511147393 56 1854 778804499 1051 17 52473...
output:
6546895
result:
ok single line: '6546895'
Test #23:
score: 6
Accepted
time: 133ms
memory: 100716kb
input:
2000 200000 200000 1999000 1499 1526 627651931 378 1689 609556194 1326 237 371224081 98 527 251964139 1280 1750 293612965 905 1848 881495354 1870 900 902279678 1496 267 634703468 59 800 164035702 109 1934 882309468 1966 702 519776748 1020 666 951531959 385 850 241053535 1211 255 903671592 66 1285 65...
output:
34222040
result:
ok single line: '34222040'
Test #24:
score: 6
Accepted
time: 381ms
memory: 139296kb
input:
2000 200000 200000 0 1820 354 521259580 1799 1723 883151663 1892 479 590713896 748 499 454440477 1752 334 983007379 56 69 157027005 554 112 225804047 1680 600 279675368 36 1372 868160579 1988 1586 523730820 35 1704 39797544 117 1627 846004390 354 1056 280474791 1736 1676 249305541 1269 111 692287711...
output:
0
result:
ok single line: '0'
Test #25:
score: 6
Accepted
time: 368ms
memory: 140648kb
input:
2000 200000 200000 1 1787 1732 413014305 1909 217 339214620 519 1338 435678958 883 831 44937921 1912 970 736120426 1190 1219 718941669 1216 1909 109658172 1849 1869 686616094 301 965 677802187 445 724 195098678 1306 1951 299168831 1970 262 204353384 1220 1409 504375659 1713 623 754436498 1452 1620 5...
output:
2
result:
ok single line: '2'
Test #26:
score: 6
Accepted
time: 406ms
memory: 143980kb
input:
2000 200000 200000 4 402 1914 269682654 675 1436 291439604 193 370 988082031 1849 1502 691456540 883 665 492038489 28 1266 573600132 1656 352 680334585 1668 1039 911608739 157 1752 964298632 979 19 526980 1113 504 262870788 126 541 220684410 269 1031 721802318 1900 1999 328920840 1770 641 692254361 ...
output:
37
result:
ok single line: '37'
Test #27:
score: 6
Accepted
time: 376ms
memory: 138984kb
input:
2000 200000 200000 26 526 1621 483988447 1703 1932 686404766 1111 1245 624032004 1457 1671 886702864 409 957 385143382 1928 1503 977317507 1319 349 983715228 401 30 251459110 245 1355 563161269 459 1436 965861604 679 949 983070365 1692 1261 456157217 698 99 409820975 1528 1362 963977301 1295 1852 79...
output:
25
result:
ok single line: '25'
Test #28:
score: 6
Accepted
time: 383ms
memory: 140008kb
input:
2000 200000 200000 625 728 133 344090289 1062 1880 597135161 844 1495 874100306 1930 389 490213163 1783 724 571192863 1499 1894 866097805 325 687 79859122 1674 1747 563976487 1940 60 855240336 1516 1087 431861062 1314 1217 250576340 646 311 63874546 647 1552 870943884 1535 1190 223697 345 1186 65344...
output:
39
result:
ok single line: '39'
Test #29:
score: 6
Accepted
time: 396ms
memory: 144620kb
input:
2000 200000 200000 4700 1725 821 429457120 1764 490 903325799 660 1294 347283520 325 16 253789876 464 1258 168173237 80 660 57504741 1136 1316 769617858 1767 1394 287008686 1824 1206 820352296 114 330 965781020 140 223 885989447 1458 742 932496684 762 1574 655017664 1598 596 723299463 1213 1898 5236...
output:
84
result:
ok single line: '84'
Test #30:
score: 6
Accepted
time: 393ms
memory: 144872kb
input:
2000 200000 200000 88061 668 1817 402362288 1250 696 637044070 1793 1147 890609254 1839 671 427058014 1636 51 777111988 567 359 308999615 1552 1510 40834395 1566 1311 738132782 271 1975 807983143 998 82 633239353 1096 843 454384442 102 1427 218117173 329 227 915637054 685 1727 911188324 1330 1175 94...
output:
652572
result:
ok single line: '652572'
Test #31:
score: 6
Accepted
time: 379ms
memory: 137828kb
input:
2000 200000 200000 533113 1338 1754 782883635 1349 1488 592703188 1645 1448 477986692 733 1042 47 981 1720 461041447 263 452 26372078 1812 765 384744847 205 372 507702235 12 1369 191909928 288 1600 812952698 1238 762 715972252 912 1876 653427552 974 1617 941376898 43 1554 514299614 220 1772 58179883...
output:
1962115
result:
ok single line: '1962115'
Test #32:
score: 6
Accepted
time: 137ms
memory: 96612kb
input:
2000 200000 200000 1999000 713 984 491810215 23 1495 711013830 1680 304 483176300 121 1907 948073782 176 89 573161170 1928 609 583837234 736 990 511532333 1734 1850 807407784 821 1402 566288558 1818 835 317847108 1824 126 439452972 1585 467 46541223 775 1709 549038510 1487 205 239467439 1096 1794 38...
output:
31758367
result:
ok single line: '31758367'
Test #33:
score: 6
Accepted
time: 71ms
memory: 100328kb
input:
995 199991 199994 128256 177 82 677669502 416 854 677166289 543 794 364534270 680 242 8 760 186 900225249 875 563 337492994 732 766 894982532 114 483 4 259 885 8 954 157 590392390 308 566 1 37 871 633804510 606 410 916672224 125 450 6 190 582 536149589 453 3 4 116 891 3 585 875 495228925 191 718 6 4...
output:
-1
result:
ok single line: '-1'
Test #34:
score: 6
Accepted
time: 74ms
memory: 102372kb
input:
996 199992 199993 124753 205 430 710291462 748 756 293873327 59 894 536099901 632 890 9 452 316 3 652 215 10 273 487 8 469 308 301806104 620 183 4 401 401 946696222 305 647 1 925 765 518528395 980 190 3 289 597 815252846 509 691 262814273 279 155 3 708 808 4 878 326 296665089 993 513 3 883 903 1 317...
output:
4319483
result:
ok single line: '4319483'
Test #35:
score: 6
Accepted
time: 74ms
memory: 96108kb
input:
997 199993 199992 124253 469 654 830723036 65 266 47739481 202 516 43614641 450 876 737667977 641 801 147893631 866 193 8 994 801 774993226 195 398 2 383 177 6 146 782 9 379 379 192058079 320 539 4 303 86 934535571 939 262 8 704 536 762562635 700 419 1 455 92 627464094 408 731 1 671 514 160757934 40...
output:
2465177
result:
ok single line: '2465177'
Test #36:
score: 6
Accepted
time: 74ms
memory: 98280kb
input:
998 199994 199991 124351 415 390 904570266 833 971 232183018 379 44 4 48 884 626169357 276 73 610900123 796 900 508923131 470 553 829096662 577 319 8 869 52 2 120 684 9 38 486 722467116 131 55 967841018 294 256 73055903 958 350 580089254 86 86 228617822 318 469 842579267 368 387 3 271 958 906176840 ...
output:
659354
result:
ok single line: '659354'
Test #37:
score: 0
Wrong Answer
time: 8ms
memory: 90084kb
input:
991 1990 1994 478740 207 85 448218904 597 457 171948410 694 916 64279329 887 773 546537318 823 474 274118886 537 337 29463181 774 790 740341746 519 263 854029433 672 88 541727414 511 529 850564468 739 665 797508491 40 659 122614430 337 219 353063113 811 126 478325496 348 587 746769857 800 169 303996...
output:
-1
result:
wrong answer 1st lines differ - expected: '1767887856', found: '-1'
Subtask #2:
score: 0
Time Limit Exceeded
Test #53:
score: 0
Time Limit Exceeded
input:
200000 100000 100000 7628995 23677 113459 839167193 165893 15365 669621527 26287 109671 214795757 156871 136723 522277985 9957 100463 806718116 104783 161385 156110975 184577 92225 545172629 57373 130083 980035338 167231 49597 919886451 115601 24325 717233004 99413 141311 737488449 83437 62759 76873...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #103:
score: 6
Accepted
time: 12ms
memory: 89700kb
input:
1 0 0 0
output:
0
result:
ok single line: '0'
Test #104:
score: 6
Accepted
time: 7ms
memory: 87776kb
input:
2 0 0 1
output:
-1
result:
ok single line: '-1'
Test #105:
score: 6
Accepted
time: 42ms
memory: 93924kb
input:
2 10 200000 1 2 1 319832429 1 1 412617159 2 1 337734185 1 2 674652880 1 2 454610992 2 2 688717944 1 1 189208056 2 2 951221780 1 2 594191431 2 2 87592160 1 2 833491749 2 2 732961971 2 1 575969648 2 2 268359887 2 1 436382098 1 2 514959278 1 2 305446083 1 2 365989813 1 2 296840111 1 1 541558213 1 1 497...
output:
10104
result:
ok single line: '10104'
Test #106:
score: 6
Accepted
time: 37ms
memory: 91752kb
input:
2 10 200000 1 1 1 1000000000 1 1 1000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 1 1 1000000000 2 1 1000000000 2 2 1000000000 2 2 1000000000 2 2 1000000000 1 1 1000000000 1 2 1000000000 1 1 1000000000 2 1 1000000000 1 1 1000000000 1 1 1000000000 2 1 1000000000 1 1 1000000000 2 2 1000000000 2...
output:
1000000000
result:
ok single line: '1000000000'
Test #107:
score: 0
Time Limit Exceeded
input:
200000 10 200000 17900 199675 76237 290240030 50211 6922 761990536 92097 120746 607490 192856 130409 616541101 50427 80049 330957286 129588 180294 466199684 8674 110653 155297749 91380 156344 798960399 102127 40858 801752583 94673 105892 152356242 185676 6183 263664373 169026 112948 812501808 93517 ...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%