QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#797149 | #9805. Guide Map | ucup-team3215 | AC ✓ | 59ms | 32240kb | C++20 | 1.9kb | 2024-12-02 17:31:03 | 2024-12-02 17:31:12 |
Judging History
answer
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 2e5, mod = 998244353, phi = mod - 1, S = 1 << 15;
int pw2[S], pwS[S];
auto& add(auto&& a, auto b) { return a -= (a += b) >= mod? mod: 0; }
auto& mul(auto&& a, auto b) { return a = a * 1ull * b % mod; }
int pw(auto&& b) { return b -= b > phi? phi: 0, mul(+pw2[b % S], pwS[b / S]); }
bool vis[N];
basic_string<int> nei[N];
void walk(int v, int p) { vis[v] = 1; for (auto u: nei[v]) if (u != p) walk(u, v); }
int ord[N], szoth;
int ft[N];
void inc(int i) { for (i = N - i - 1; i < N; i |= i + 1) ++ft[i]; }
int que(int i) { int x = 0; for (i = N - i - 1; i; i &= i - 1) x += ft[i - 1]; return x; }
int cd[N], ss[N];
void down(int v, int p) {
int t;
cd[v] -= t = que(v), inc(v);
for (auto u: nei[v]) if (u != p) down(u, v), (ss[v] += ss[u] + cd[u]) %= phi, cd[u] -= t, cd[u] += t = que(v);
cd[v] += t;
}
void up(int v, int p) {
for (auto u: nei[v]) if (u != p) {
ss[u] = (szoth - ord[v] + ss[v] + phi - cd[u]) % phi;
up(u, v);
}
}
int ans;
void solve(int v, int p, int cur) {
add(ans, pw(cur));
for (auto u: nei[v]) if (u != p) solve(u, v, cur + szoth - ord[u]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (int i = 0, p = 1; i < S; ++i) pw2[i] = p, add(p, p);
for (int i = 0, p = 1, t = mul(2, pw2[S - 1]); i < S; ++i) pwS[i] = p, mul(p, t);
int n; cin >> n;
for (int i = 2, a, b; i < n; ++i) cin >> a >> b, nei[--a].push_back(--b), nei[b].push_back(a);
walk(0, 0);
int r;
for (int i = 0; i < n; ++i) ord[i] = ord[i - !!i] + !vis[i], r = vis[i]? r: i;
szoth = ord[n - 1];
down(0, 0);
down(r, r);
up(r, r);
int c = 0;
for (int i = 0, j = szoth; i < n; ++i) if (!vis[i]) add(c, pw(--j + ss[i] + ss[0]));
solve(0, 0, 0);
cout << add(mul(ans, c), (szoth == 1) * pw(ss[0])) << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 10800kb
input:
4 1 4 2 3
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 10260kb
input:
2
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 2ms
memory: 11004kb
input:
4 1 2 1 3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 0ms
memory: 10244kb
input:
4 1 3 3 2
output:
8
result:
ok 1 number(s): "8"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11236kb
input:
4 1 4 4 2
output:
5
result:
ok 1 number(s): "5"
Test #6:
score: 0
Accepted
time: 2ms
memory: 11300kb
input:
4 1 2 3 4
output:
15
result:
ok 1 number(s): "15"
Test #7:
score: 0
Accepted
time: 0ms
memory: 11168kb
input:
4 3 2 2 4
output:
10
result:
ok 1 number(s): "10"
Test #8:
score: 0
Accepted
time: 3ms
memory: 12160kb
input:
5000 407 334 4311 4338 2530 2578 2052 1946 3803 3961 1849 1756 813 876 1417 1364 3955 3713 694 661 2682 2791 1626 1791 3913 3702 4068 4053 1239 1264 2848 2682 4995 4979 3609 3604 3496 3434 229 162 4178 4769 3908 3874 4891 4920 2401 2249 2682 2853 4294 4336 4494 4478 2815 2682 4925 4928 912 914 2257 ...
output:
574627696
result:
ok 1 number(s): "574627696"
Test #9:
score: 0
Accepted
time: 4ms
memory: 11572kb
input:
5000 4737 4822 2534 2241 724 710 1628 1749 4448 4435 3571 4046 4029 4064 4972 4949 4405 4346 3929 4150 630 546 207 246 3203 3182 880 877 2200 2306 4336 4365 74 126 3932 3777 4212 4210 753 418 4995 4960 274 644 3993 4081 1522 1458 1937 1887 3882 4124 3651 4038 2703 2630 1918 1912 2764 2832 171 137 48...
output:
844318380
result:
ok 1 number(s): "844318380"
Test #10:
score: 0
Accepted
time: 3ms
memory: 12072kb
input:
5000 4016 3910 4361 4417 3103 3026 4686 4701 595 592 3076 3071 859 931 4288 4262 4478 4452 4884 4982 3595 3550 2814 2821 3521 3437 872 925 3785 3836 1192 1094 4149 4133 3603 3467 2999 3031 2425 2289 379 376 932 952 1483 1436 144 190 2619 2630 2078 2067 3226 3173 2996 2931 4520 4461 2724 2790 2475 24...
output:
928056438
result:
ok 1 number(s): "928056438"
Test #11:
score: 0
Accepted
time: 0ms
memory: 10460kb
input:
5000 1714 1797 3971 4077 2321 2302 3844 3211 3852 3900 865 908 2586 2565 2311 2122 3320 3089 2113 2200 3101 3798 3192 3024 1687 1490 3194 3772 210 264 80 147 4309 4225 3017 2854 1861 1511 3207 3307 4395 4438 2138 2204 3459 3624 1670 1518 4175 3959 2087 2078 1128 1097 1770 1574 840 833 1298 1207 2056...
output:
289973060
result:
ok 1 number(s): "289973060"
Test #12:
score: 0
Accepted
time: 3ms
memory: 12092kb
input:
5000 4970 1539 4964 4066 3800 2291 3101 2220 4718 1242 4970 4489 3275 1183 1645 2209 4970 3628 1874 2720 3392 4356 1227 4970 306 1131 293 2057 1980 4500 336 3792 4970 4588 3826 3933 336 3786 3589 2148 717 1369 3589 3595 336 1916 4970 3447 4970 529 2570 4012 2049 4970 2282 336 3097 2495 4787 424 4970...
output:
747571707
result:
ok 1 number(s): "747571707"
Test #13:
score: 0
Accepted
time: 3ms
memory: 10664kb
input:
5000 2059 75 1737 2687 4712 2259 4792 2059 4990 3387 705 3561 4128 2059 2059 1676 2910 196 4371 4262 3332 3286 3168 2048 4368 2907 1154 3951 496 4358 4988 2059 2059 4905 4640 2155 318 3306 2492 2753 128 4624 239 919 1891 4990 2851 2622 2009 2059 4260 3788 3597 1389 1169 919 4691 4597 4990 4410 1826 ...
output:
728916312
result:
ok 1 number(s): "728916312"
Test #14:
score: 0
Accepted
time: 3ms
memory: 10972kb
input:
5000 28 964 2373 1620 1693 3860 2179 4699 3661 516 1420 4579 430 42 822 3550 4746 1837 498 4426 2887 725 1587 1731 4895 2648 1093 2701 985 626 1980 2449 4675 1550 1940 2309 2217 3178 2310 3364 3469 4708 4598 1729 93 1759 4061 2641 1420 2563 4349 2993 4411 2445 4710 728 4726 4188 2026 1291 4916 824 2...
output:
600365554
result:
ok 1 number(s): "600365554"
Test #15:
score: 0
Accepted
time: 0ms
memory: 12480kb
input:
5000 674 2007 3824 1699 2977 1519 4900 545 4798 4617 913 3691 4352 2068 164 2412 2018 4524 2306 672 389 2543 1114 4254 555 1250 1070 21 2850 4335 2977 1785 505 2092 1972 400 3727 3947 3050 25 3235 1158 4338 2130 2185 3824 1680 1370 770 4872 2977 4259 2624 398 4571 3666 3345 4674 4404 428 56 541 2561...
output:
117462685
result:
ok 1 number(s): "117462685"
Test #16:
score: 0
Accepted
time: 0ms
memory: 12064kb
input:
5000 536 1522 3240 4848 2425 680 4827 3759 2522 2634 3061 1006 1422 1374 4768 3745 4528 3589 995 3473 649 716 3738 3542 911 3572 1714 1275 4257 1054 1267 4563 2198 3255 4585 4704 1686 2681 1873 2994 4726 1731 2986 4117 1170 2808 1943 2850 905 4774 1931 3841 246 2593 2502 543 2605 4403 1206 4702 2199...
output:
973970642
result:
ok 1 number(s): "973970642"
Test #17:
score: 0
Accepted
time: 0ms
memory: 11124kb
input:
5000 772 3375 4913 3401 4995 515 3179 2902 3284 475 3658 2590 3549 2308 910 2606 680 185 509 90 1924 4153 2011 4656 4000 68 3429 4147 4605 1481 965 4241 4995 2696 3135 12 4034 4002 3091 2838 57 1555 2835 602 4828 1229 4729 155 4702 3040 1057 1851 2025 3088 2678 4555 2252 1493 4086 2591 3781 1204 183...
output:
427070782
result:
ok 1 number(s): "427070782"
Test #18:
score: 0
Accepted
time: 3ms
memory: 10312kb
input:
5000 4445 91 4892 3144 2211 2563 2870 3754 550 4912 1989 1100 106 3681 1330 952 3652 920 1929 3103 3103 323 4418 3103 3632 4006 3103 1282 3103 1672 322 1734 3103 1780 325 3652 3103 4647 3652 1314 3652 81 746 168 1823 3247 1099 64 4697 2107 347 3176 4572 3200 204 4136 3103 1052 2771 1082 430 3103 310...
output:
984937631
result:
ok 1 number(s): "984937631"
Test #19:
score: 0
Accepted
time: 3ms
memory: 11748kb
input:
5000 2762 4174 3749 4061 2401 4137 3509 87 738 4912 2125 122 1629 92 329 2565 929 4966 1078 4233 466 2498 716 2596 3664 898 3320 2349 1865 4545 1642 3289 4958 843 3923 2840 4265 3954 425 1203 2640 596 3882 880 92 4141 1643 2079 3406 2296 3121 3219 1204 3547 3804 984 92 4250 4214 3202 2972 3278 3512 ...
output:
944816617
result:
ok 1 number(s): "944816617"
Test #20:
score: 0
Accepted
time: 0ms
memory: 10792kb
input:
5000 4113 1739 3973 1451 2460 3070 3293 445 1731 4615 1245 3345 2839 3050 977 3596 1370 4639 3160 2231 731 1137 2217 3625 2555 4018 4590 3946 2081 2436 4737 1996 574 3142 2885 3317 1422 4527 2342 2047 210 236 1155 3361 4920 4224 1265 2526 3303 2425 2327 1641 1892 3579 4439 2996 442 196 427 702 2307 ...
output:
257696103
result:
ok 1 number(s): "257696103"
Test #21:
score: 0
Accepted
time: 0ms
memory: 10932kb
input:
5000 3211 1670 1086 2203 2311 2995 1660 2918 4685 500 4437 2425 4941 4896 2697 2535 1051 510 3015 3300 190 1381 2074 2181 5000 3799 2638 2097 974 2152 3719 3341 1064 4568 2345 4712 3255 2205 90 2206 2929 465 2364 2069 295 1035 2506 3915 4129 718 4603 1390 256 2845 1600 3283 4420 3287 3388 4131 739 6...
output:
90790805
result:
ok 1 number(s): "90790805"
Test #22:
score: 0
Accepted
time: 0ms
memory: 12400kb
input:
5000 3950 571 1358 753 2584 2176 1982 934 2977 2775 4061 3191 3757 67 2787 4223 2512 1991 1077 2815 1394 3481 371 336 2282 4211 2175 1021 1806 4564 1920 601 3342 1526 3402 2419 310 231 3295 4403 4337 216 4068 3799 4728 4309 3703 4668 541 4204 4501 1916 132 831 793 2791 4188 4731 1485 4305 3968 2197 ...
output:
348148683
result:
ok 1 number(s): "348148683"
Test #23:
score: 0
Accepted
time: 3ms
memory: 11288kb
input:
5000 4686 4000 2056 3139 703 3076 4552 1909 2446 214 1454 923 717 187 851 3828 721 1436 1442 1907 513 547 161 4222 1388 4491 861 4494 983 4977 3741 3860 623 4069 3862 539 1957 4795 1157 4347 1202 1908 260 3767 3878 3611 4032 4218 984 2786 4163 3215 1347 4862 3118 2005 4171 1335 274 4756 959 3982 270...
output:
137895194
result:
ok 1 number(s): "137895194"
Test #24:
score: 0
Accepted
time: 40ms
memory: 15204kb
input:
200000 193646 193124 136401 140362 152430 149598 107317 106567 192382 192315 60375 61977 159553 160535 11641 11511 190147 189847 55014 52591 70317 88588 11641 25917 48335 45757 116921 124433 57211 50687 122916 122332 198934 198765 16631 11641 198103 198367 83133 68761 87932 69386 39246 38657 177413 ...
output:
727927914
result:
ok 1 number(s): "727927914"
Test #25:
score: 0
Accepted
time: 39ms
memory: 15704kb
input:
200000 12166 11726 137283 142820 31053 35541 106694 101141 26851 25452 56714 53513 110221 110912 163816 161984 95516 93488 113051 118110 62456 61874 16568 9043 183305 182485 1740 5440 35037 33177 125158 132799 68398 61536 141916 142669 104690 108054 7490 19341 63290 68761 44904 43782 76573 79270 154...
output:
483662812
result:
ok 1 number(s): "483662812"
Test #26:
score: 0
Accepted
time: 35ms
memory: 15640kb
input:
200000 121578 120778 166046 166804 63008 62707 172805 180182 121452 139614 186476 185972 139628 124358 80298 84225 157354 159700 149701 148093 127373 122225 144050 144025 47004 47069 176483 169839 99607 95182 1764 1602 79431 74006 175002 179584 56326 56144 179379 170975 54222 50474 85395 84148 65784...
output:
461047062
result:
ok 1 number(s): "461047062"
Test #27:
score: 0
Accepted
time: 50ms
memory: 15872kb
input:
200000 100775 100063 87081 108100 156436 177193 136419 136502 139323 139673 125338 124601 148748 151484 6706 1509 163197 173317 146956 147663 62587 62420 81191 81353 4474 6228 139615 139323 51121 51985 134049 131468 34899 37105 14703 8157 188866 188888 32458 33525 74150 68029 137091 137161 80703 807...
output:
323976684
result:
ok 1 number(s): "323976684"
Test #28:
score: 0
Accepted
time: 46ms
memory: 15384kb
input:
200000 75154 77487 74797 73738 91922 94229 71371 71042 112758 113514 83514 81684 77032 77997 141158 145688 24403 23868 168468 168980 109670 105380 100741 100810 75991 78681 3228 3208 195981 191953 105030 106739 118015 118706 65451 65639 33558 29789 88536 88054 49710 50037 70248 71371 148635 148363 2...
output:
731876547
result:
ok 1 number(s): "731876547"
Test #29:
score: 0
Accepted
time: 42ms
memory: 15196kb
input:
200000 130054 137125 114908 112689 30722 30316 67448 68098 170624 170271 182824 176800 108903 109437 186356 186394 59620 57261 101903 101154 27387 22793 2699 6573 1222 1453 182824 176963 99804 101903 182824 180038 59985 58789 101903 91549 49887 49522 155267 155107 83041 83324 34374 34913 195060 1921...
output:
553939859
result:
ok 1 number(s): "553939859"
Test #30:
score: 0
Accepted
time: 35ms
memory: 14988kb
input:
200000 4894 6412 53545 54035 140736 136599 124060 124370 171469 168053 23289 23894 96807 97678 95096 94433 140927 144000 110339 98460 185717 185849 182300 184326 87783 81857 63094 61735 106047 97160 89453 89552 58628 57920 196407 196040 139563 143609 49826 49878 61905 62598 196040 199845 88191 81119...
output:
500537103
result:
ok 1 number(s): "500537103"
Test #31:
score: 0
Accepted
time: 47ms
memory: 15696kb
input:
200000 100795 106977 86271 105796 145926 148854 178640 178182 6112 4817 55775 58052 13027 14571 127124 126379 103851 106050 131318 124208 68080 62774 41473 41924 87128 93531 26758 26803 97660 90205 179072 178640 124567 121774 48470 49694 162758 175257 16228 16207 114627 112472 8004 6214 58789 61707 ...
output:
611869539
result:
ok 1 number(s): "611869539"
Test #32:
score: 0
Accepted
time: 41ms
memory: 15540kb
input:
200000 144258 141041 93073 93160 105417 102924 8321 9035 182623 185868 46196 43971 52347 42632 182623 184969 69375 66549 182623 169919 52853 52535 149368 152025 2352 2356 123602 131028 183063 182623 177813 182623 50029 42593 141719 141963 85309 90867 117329 116147 74059 73804 134444 124516 102816 10...
output:
434720350
result:
ok 1 number(s): "434720350"
Test #33:
score: 0
Accepted
time: 43ms
memory: 14824kb
input:
200000 151689 138003 179765 113024 5801 27701 65969 193663 132677 83473 19409 110898 111101 146648 153845 41675 179244 181208 159170 41675 41675 131782 41675 156968 61313 43871 163483 59686 18972 175803 47468 24912 112068 103639 117244 41675 124400 5560 86058 93328 27819 147912 41675 177562 137345 1...
output:
694969257
result:
ok 1 number(s): "694969257"
Test #34:
score: 0
Accepted
time: 55ms
memory: 19144kb
input:
200000 129630 181282 112751 67798 92719 165324 108349 87950 18431 11840 87478 63835 79012 70121 28514 53132 61786 9873 136685 86715 121776 9397 181601 194414 159260 172551 6548 147570 159198 199950 88739 68208 77570 157998 38786 26167 46136 198855 33059 156449 11200 46835 104770 186167 23678 29667 1...
output:
903773595
result:
ok 1 number(s): "903773595"
Test #35:
score: 0
Accepted
time: 56ms
memory: 22272kb
input:
200000 118699 136408 17053 46361 37038 167068 123157 76040 56143 184706 196149 3987 89677 91756 24232 26908 115752 14628 64501 164190 92709 176309 138154 80618 130369 53312 164118 134823 54852 61337 57976 84207 133086 85576 102789 14578 112502 19956 130804 27897 156955 73854 192140 149302 91583 1493...
output:
151531259
result:
ok 1 number(s): "151531259"
Test #36:
score: 0
Accepted
time: 59ms
memory: 25356kb
input:
200000 173980 7891 88130 111730 198966 51703 140531 6174 95854 148987 127993 4468 31962 98444 129376 36332 92173 168662 11772 170597 105371 81842 141731 21913 93951 177228 27473 195489 103865 29472 113048 29240 91754 78199 162486 131228 81343 16925 63887 87959 37924 10213 36000 140391 146625 103762 ...
output:
147972383
result:
ok 1 number(s): "147972383"
Test #37:
score: 0
Accepted
time: 50ms
memory: 28796kb
input:
200000 97770 19875 29223 165934 182993 9628 108676 128716 34460 178839 52027 114763 126978 91049 38526 188293 10727 136637 93230 154363 75593 49771 15691 84647 31171 163308 5401 120509 163729 10736 67154 23878 96838 91654 112778 168655 126032 95125 138444 119576 83775 171297 186153 52398 106299 1247...
output:
591735912
result:
ok 1 number(s): "591735912"
Test #38:
score: 0
Accepted
time: 53ms
memory: 32240kb
input:
200000 75986 100005 17232 91894 120393 101065 180948 65437 133793 101336 31389 43095 122391 132549 16966 193965 24665 170134 124745 177925 170330 156646 94477 157154 190849 89357 46332 78982 90622 138103 166835 165736 192433 29453 157483 129126 83211 150070 124954 145345 140339 175748 91897 83125 19...
output:
991050818
result:
ok 1 number(s): "991050818"
Test #39:
score: 0
Accepted
time: 48ms
memory: 15372kb
input:
200000 32829 121233 29146 62140 158405 74698 185917 26733 163896 150236 145204 54213 2526 104991 37305 23594 157165 133687 108857 56391 146801 1947 72151 49147 86561 135448 12241 135880 191559 148214 85652 96094 178121 15128 183810 129508 195609 191507 21500 102757 68962 156731 154830 65808 144788 1...
output:
362050546
result:
ok 1 number(s): "362050546"
Test #40:
score: 0
Accepted
time: 42ms
memory: 16264kb
input:
200000 158678 56306 150217 38492 119262 8785 2420 2164 14836 6692 39442 166053 8195 8785 148729 199179 148687 124720 147547 95352 129284 110183 95818 133414 74970 84878 106604 135311 151236 8272 147534 196487 33322 70844 17474 162953 192834 150217 134287 150217 192552 11839 172854 169380 47852 11520...
output:
641283427
result:
ok 1 number(s): "641283427"
Test #41:
score: 0
Accepted
time: 54ms
memory: 21460kb
input:
200000 168742 110785 3016 108963 39711 132059 149669 71665 57403 7883 60071 101707 48208 188588 14665 75722 129805 17926 110511 48489 129276 110581 70407 55870 150963 183497 24929 137775 137255 79625 55771 190981 182922 164326 52691 38044 30928 137582 34586 30301 33072 194060 130981 72280 159219 417...
output:
440430277
result:
ok 1 number(s): "440430277"
Test #42:
score: 0
Accepted
time: 40ms
memory: 24912kb
input:
200000 51065 87259 80194 160352 87353 145155 161571 18352 105409 194959 193463 76990 158539 192211 129619 174564 125516 28414 175748 28144 64428 124171 96215 185077 58932 71516 26867 109640 27159 193057 85870 106422 191975 58828 128481 186326 41437 67261 107484 70677 21723 139575 158256 35170 179515...
output:
439078240
result:
ok 1 number(s): "439078240"
Test #43:
score: 0
Accepted
time: 48ms
memory: 26388kb
input:
200000 96987 94094 120906 91418 13164 166017 120954 13527 193912 20904 144661 112053 63214 3262 51288 27201 69777 123527 25889 153638 129853 61839 66218 44838 19214 13187 27957 67209 5802 136568 77933 137987 166848 22829 82927 18499 106883 122324 87110 17860 121569 166887 136252 154456 149005 112075...
output:
70916748
result:
ok 1 number(s): "70916748"
Test #44:
score: 0
Accepted
time: 55ms
memory: 31836kb
input:
200000 153443 142854 97331 146374 67670 84177 97823 40284 107785 25819 25486 6716 67384 62036 84830 104660 140050 58653 151899 156979 48929 12811 109552 19991 62547 59286 75910 172639 5076 56644 70860 198157 189147 49401 185216 135114 68314 171996 185243 105350 185761 101962 32069 199834 114040 1416...
output:
683287273
result:
ok 1 number(s): "683287273"
Test #45:
score: 0
Accepted
time: 32ms
memory: 32052kb
input:
200000 200000 199999 199999 199998 199998 199997 199997 199996 199996 199995 199995 199994 199994 199993 199993 199992 199992 199991 199991 199990 199990 199989 199989 199988 199988 199987 199987 199986 199986 199985 199985 199984 199984 199983 199983 199982 199982 199981 199981 199980 199980 199979...
output:
943946736
result:
ok 1 number(s): "943946736"
Test #46:
score: 0
Accepted
time: 32ms
memory: 32188kb
input:
200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
64266001
result:
ok 1 number(s): "64266001"
Extra Test:
score: 0
Extra Test Passed