QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #491316 | #8533. Island Vacation | green_gold_dog# | 30.434783 | 5ms | 4668kb | C++20 | 2.3kb | 2024-07-25 18:42:47 | 2024-07-25 18:42:47 |
Judging History
answer
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = true;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
ll binpow(ll a, ll b) {
return (b == 0 ? 1 : square(binpow(a, b / 2)) % MOD * (b % 2 ? a : 1) % MOD);
}
ll inv(ll x) {
return binpow(x, MOD - 2);
}
void dfs(ll v, ll p, vector<ll>& ps, vector<vector<pair<ll, bool>>>& g, vector<ll>& ans, ll now, vector<ll>& invs) {
ans[v] = (ans[v] + now * ps[v]) % MOD;
now = (now - now * ps[v] % MOD + MOD) % MOD;
ll col = 0;
for (auto&[i, b] : g[v]) {
if (i == p) {
b = true;
}
if (b) {
continue;
}
col++;
}
if (col == 0) {
ans[v] = (ans[v] + now) % MOD;
}
now = now * invs[col] % MOD;
for (auto&[i, b] : g[v]) {
if (b) {
continue;
}
b = true;
dfs(i, v, ps, g, ans, now, invs);
b = false;
}
for (auto&[i, b] : g[v]) {
if (i == p) {
b = false;
}
}
}
void solve() {
ll n, m;
cin >> n >> m;
vector<ll> ps(n);
vector<ll> invs(n, 0);
for (ll i = 0; i < n; i++) {
invs[i] = inv(i);
cin >> ps[i];
}
vector<vector<pair<ll, bool>>> g(n);
for (ll i = 0; i < m; i++) {
ll a, b;
cin >> a >> b;
a--;
b--;
g[a].emplace_back(b, false);
g[b].emplace_back(a, false);
}
vector<ll> ans(n, 0);
dfs(0, 0, ps, g, ans, 1, invs);
for (auto i : ans) {
cout << i << ' ';
}
cout << '\n';
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
詳細信息
Pretests
Final Tests
Test #1:
score: 4.34783
Accepted
time: 0ms
memory: 3596kb
input:
2 3 2 0 10 111111112 1 3 2 3 6 5 500000004 0 0 0 0 0 1 5 1 3 4 5 5 6 1 2
output:
0 888888896 111111112 500000004 166666668 166666668 83333334 0 83333334
result:
ok 2 lines
Test #2:
score: 4.34783
Accepted
time: 0ms
memory: 3600kb
input:
2 5 5 333333336 333333336 0 0 0 1 2 2 3 3 4 4 5 1 5 5 5 0 0 0 0 0 1 2 2 3 2 4 1 4 1 5
output:
777777784 222222224 0 0 0 0 0 333333336 0 666666672
result:
ok 2 lines
Test #3:
score: 4.34783
Accepted
time: 0ms
memory: 3832kb
input:
1 11 13 2 3 4 5 6 7 8 9 10 11 12 1 2 1 3 2 3 2 4 4 5 2 5 4 8 5 9 2 6 6 7 2 7 6 10 5 11
output:
133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18
result:
ok single line: '133332478 200000394 577778352 ...5536 800000020 18 600000029 18 '
Test #4:
score: 4.34783
Accepted
time: 1ms
memory: 3536kb
input:
10 9 10 156241079 379541254 371589355 610239128 49714057 421621164 578509177 629476125 959162361 1 4 8 9 3 4 2 8 1 6 2 5 4 8 4 7 7 8 5 9 10 11 374116260 83263449 755436519 419356370 199185436 630946701 202626825 769874541 945053459 202188252 2 8 4 6 1 4 8 9 2 9 1 9 7 10 2 5 7 9 3 5 6 9 11 11 5912...
output:
156241079 581022743 917237336 654090753 283516650 921879468 36045205 510422725 939544077 14791903 324370756 795356662 831332131 534525350 270628991 8908779 48718773 415755370 755611314 751902387 768822757 959033672 355792462 245288036 935578463 489434854 652999373 507116973 37886731 296144335 816...
result:
ok 10 lines
Test #5:
score: 4.34783
Accepted
time: 1ms
memory: 3760kb
input:
10 9 11 211755593 863978352 292138943 850121258 174200766 76231890 125090458 818563596 501765461 8 9 5 7 1 9 6 7 3 7 2 8 2 5 1 8 7 8 4 7 4 6 10 12 271033216 545744125 536383199 238394424 897610574 935057864 648703551 389007542 351081312 607139124 1 3 5 7 4 8 3 5 6 7 3 8 2 6 5 6 5 8 6 9 3 10 2 9 1...
output:
308621652 883968415 982169568 480461004 299439877 167332397 856003736 570294439 451708948 271033216 854149255 837985588 823436460 599878312 464230393 751236846 123410292 744105781 530533900 578164881 767285306 379875233 915480421 650692454 294277865 348663529 201562287 919604012 593874866 35051918...
result:
ok 10 lines
Test #6:
score: 4.34783
Accepted
time: 5ms
memory: 4100kb
input:
3 94 93 716690368 156752297 913895827 268482677 882522602 547160853 389245810 375523323 895105390 254424101 538701151 198984912 807025679 346803749 571407109 783756836 693285484 906928732 926915106 761785975 613428534 858135966 714778886 215343323 22512420 614632073 510503478 32904507 140760828 125...
output:
716690368 491679565 637840709 538350901 690574815 269938364 243685817 458958906 815665672 519562661 615911790 141654820 493889248 608407455 847798640 701288661 364776560 85334189 463787785 471574345 208681594 159291344 589989537 239461173 895901419 368710406 733002790 531604221 80318687 672241116 33...
result:
ok 3 lines
Test #7:
score: 4.34783
Accepted
time: 5ms
memory: 4668kb
input:
1 10000 9999 576833221 741254435 117793269 701925229 22005656 239319661 86240344 105803398 467040969 756270105 116085215 861940373 149801070 899613063 392056836 99256548 852081659 560316430 196449470 531625852 642203107 358691908 324421505 235340103 951148812 605308763 135005889 485412373 381878573...
output:
576833221 704835499 908335047 55512117 141643172 511388 685927479 656482926 136091930 702025696 812206778 596850592 355757127 24257657 277465547 830233158 611587321 301146489 840322512 18820205 798926467 578897563 356138711 681255183 761206632 358195149 912681865 897565004 804247230 949827105 654674...
result:
ok single line: '576833221 704835499 908335047 ...0 333679124 44781812 862486337 '
Test #8:
score: 0
Time Limit Exceeded
input:
1 10000 10943 32326933 812025401 210221546 72620980 657376233 724392018 207844388 190240185 256584719 981809953 974774894 381130090 244450463 990354318 76848594 851516602 806739060 159702372 658590506 478233241 418138741 748284798 980526211 421898568 493428394 506703542 546699994 372003968 51934363...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
3 1897 2095 474609288 779474631 779968093 949761404 645301315 770889157 472994134 972074110 289308071 761535595 905289229 732065100 461703861 775513058 340348205 888480327 12015066 695547901 530980608 622881300 397044812 278294723 969766632 547059540 97912827 508554679 677806412 697750963 740912427...
output:
474609288 231598073 902601855 112471498 339547454 688867415 421431814 742177889 945075063 405075705 706552396 732235506 414447531 301182980 312107337 62885880 256074114 443124719 490827230 76158595 346230129 532979522 910928845 778311727 835414044 806311075 47693554 604699625 557533901 828210816 598...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
1 10000 13332 23272604 106456403 552404970 340873196 441725266 584537931 651297537 554527114 999835377 291169171 881406071 293435749 796999561 286225242 138053764 84588107 774407928 243711779 963791106 183787711 671593095 70037130 624801729 751631248 434538704 188398359 443667223 966614161 85295170...
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
3 1463 1949 804075450 849001569 780226578 84218572 585348631 201620704 903592060 23034348 422772787 993091934 962575074 61498354 989261183 926127854 440326688 25255594 880702106 703894076 759539186 219684073 448090899 848745334 41033887 23369774 848538087 525349972 700977795 312630799 995834542 498...
output:
292521922 287624275 52496488 778866419 97573245 527601913 990242946 529894483 472373168 349032035 492532499 650058057 41168188 902576127 844636275 770653245 422016414 424156255 677069591 268144613 373420067 849387243 144042645 61267179 656937281 731569093 713034482 273998296 879458379 279549595 2862...
result:
Test #12:
score: 0
Time Limit Exceeded
input:
1 10000 10314 399981704 350800784 166636544 179853806 33042404 86064863 213399756 312153691 697964372 305222600 196959690 226031215 963691253 793135536 591358392 191194147 608131246 729569240 6701657 136288535 904248767 745750756 19509028 505742117 798834348 243275344 694690379 912671715 519316986 ...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
1 10000 14544 74244896 339306242 50020755 817510228 460696636 469808051 155933575 635899119 633244980 365257928 938421332 496186863 652825873 852388335 726192462 669683699 599562596 893542248 778944170 486074660 787965049 635147678 895809246 752247698 791419586 34270072 616383249 497619068 11727106...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
3 364 400 184831392 322857279 815903253 677965630 300678967 534281908 628461087 590429679 889408867 408654891 346772772 481156318 158940706 878527590 480738355 13123287 910680778 416919745 131908371 188483119 223576496 422098383 787040434 0 0 779889009 993807563 973938011 834203840 1 315303008 5082...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
3 1466 1531 922720536 629005703 983240032 350947246 256000722 698679004 211654861 114036597 144399752 167026536 463996486 959705855 444763005 762417508 902715477 673468121 814048083 831832585 852519594 962453264 698959544 549808404 25414406 596842459 774662962 151620087 315149306 150690213 48227968...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
1 10000 11944 166332897 341402193 451476981 645601935 482996064 569288854 341776560 764393689 123072751 697995816 818881168 844852925 757125373 534760733 132649601 173135023 436697832 920849536 560157881 51022469 790686244 514595504 23439740 899847037 39148078 952261186 535804075 732068812 30737645...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
1 10000 14949 445807845 41486003 292461319 274447930 43586742 144184961 955726447 947906702 93907878 581784067 994565884 161051925 732155319 791242435 846379763 387787485 541540074 133657525 685358635 545069356 512884308 905261280 279831247 311038063 96641269 887491773 532513403 320280052 370115839...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
3 7486 9123 679044939 745060822 0 313853244 876616276 936686875 1 0 8976877 832106117 0 894950509 170920333 774065740 5745899 1 40140693 819071291 739212251 264988399 230242604 527185147 1 964361570 5881486 0 655753319 97038172 426215540 17105579 787299330 149316908 650945053 690554987 1 0 55328239...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
3 9370 11268 711164105 899197102 908629715 992902809 943431188 609929773 77613267 572629631 788655576 798308211 783848959 694196642 62749095 605955347 307236329 184523040 364909367 975570957 151013015 519964435 179076548 407077650 769844263 589544128 216032694 601855730 784780715 191280132 67033245...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
1 10000 12847 585012089 726215459 776197761 922407522 398972335 484628127 295766050 141203789 116692194 502371103 168110238 386261109 35623016 13366467 183431163 330814985 953858754 458313028 600518660 874199097 265910691 227369704 605751023 350837817 284169231 756465321 30989650 73813278 36419077 ...
output:
result:
Test #21:
score: 0
Time Limit Exceeded
input:
1 9999 14997 371850406 180293163 766550290 103212526 214392166 480536182 886359647 722393262 516379312 491364272 992896955 234121831 225964011 333870959 53013555 300758030 550735207 761508243 142390810 211672008 520918181 322706826 270746552 581930565 235876328 138636406 250966133 171731449 7853759...
output:
result:
Test #22:
score: 0
Time Limit Exceeded
input:
3 2410 3031 1 588007765 481177480 105433833 338665365 0 498728825 725924281 37780399 545378609 722178352 241964165 592727002 603929094 290265987 380121207 275039311 280349076 908897674 447313439 417618597 169373313 1 291590307 396387463 1 523153881 363071402 87700312 677133009 184538157 483311743 6...
output:
result:
Test #23:
score: 0
Time Limit Exceeded
input:
3 1915 2257 395987795 839404392 822192278 160521894 178536377 650067511 4008417 449173588 64992895 839129530 467233849 544539113 992200696 776511262 703389882 94540936 223154898 426250698 745794557 796582959 315916002 112141394 227297480 520374973 347500285 184823868 750987257 627912504 779610299 7...