QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #55081 | #1217. 归程 | Steven_lzx | 100 ✓ | 2250ms | 184684kb | C++17 | 3.3kb | 2022-10-12 09:27:03 | 2022-10-12 09:27:04 |
Judging History
answer
//P4768 [NOI2018] 归程
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=800050,MAXM=800080;
struct Node
{
int u,v,h;
}edge[MAXM];
struct Edge
{
int to,nxt;
ll w,h;
}span[MAXM];
ll n,m,s,k,t,q,ans,dis[MAXN],cnt,num,head[MAXN],fa[MAXN],f[MAXN][21],low[MAXN],val[MAXN];
bool vis[MAXN];
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >h;
bool operator <(Node a,Node b)
{
return a.h>b.h;
}
void addedge(int a,int b,ll c,ll d)
{
span[++cnt].nxt=head[a];
head[a]=cnt;
span[cnt].to=b;
span[cnt].w=c;
span[cnt].h=d;
return;
}
void dijkstra()
{
int u,v;
memset(dis,111,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[1]=0;
h.push(make_pair(0,1));
do
{
u=h.top().second;
h.pop();
if(vis[u])
{
continue;
}
vis[u]=true;
for(int i=head[u];i;i=span[i].nxt)
{
v=span[i].to;
if(dis[u]+span[i].w<dis[v])
{
dis[v]=dis[u]+span[i].w;
h.push(make_pair(dis[v],v));
}
}
}
while(!h.empty());
return;
}
ll find(ll x)
{
return (x==fa[x]?x:fa[x]=find(fa[x]));
}
void dfs(int u)
{
int v;
low[u]=dis[u];
for(int i=head[u];i;i=span[i].nxt)
{
v=span[i].to;
f[v][0]=u;
dfs(v);
low[u]=min(low[u],low[v]);
}
return;
}
void kruskal()
{
int x,y;
cnt=0;
memset(head,0,sizeof(head));
sort(edge+1,edge+m+1);
for(int i=1;i<=m;i++)
{
x=find(edge[i].u);
y=find(edge[i].v);
if(x==y)
{
continue;
}
num++;
fa[x]=fa[y]=fa[num]=num;
addedge(num,x,0,0);
addedge(num,y,0,0);
val[num]=edge[i].h;
}
dfs(num);
for(int j=1;(1<<j)<=num;j++)
{
for(int i=1;i<=(n<<1);i++)
{
f[i][j]=f[f[i][j-1]][j-1];
}
}
return;
}
int main()
{
int a,b;
ll c,d;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
ans=cnt=0;
memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
memset(low,111,sizeof(low));
num=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld%lld",&a,&b,&c,&d);
edge[i].u=a;
edge[i].v=b;
edge[i].h=d;
addedge(a,b,c,d);
addedge(b,a,c,d);
}
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
scanf("%lld%lld%lld",&q,&k,&s);
dijkstra();
kruskal();
while(q--)
{
scanf("%lld%lld",&c,&d);
c=(c+k*ans-1)%n+1;
d=(d+k*ans)%(s+1);
for(int i=20;~i;i--)
{
if(f[c][i]&&val[f[c][i]]>d)
{
c=f[c][i];
}
}
printf("%lld\n",ans=low[c]);
}
}
return 0;
}
/*
* 洛谷
* https://www.luogu.com.cn/problem/P4768
* C++20 -O0
* 2022.10.11
*/
详细
Test #1:
score: 5
Accepted
time: 74ms
memory: 153932kb
input:
3 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1
output:
result:
ok 0 lines
Test #2:
score: 5
Accepted
time: 66ms
memory: 153884kb
input:
3 6 9 1 6 395 1 6 3 13 1 6 4 798 1 6 5 403 1 4 5 2 1 3 1 97 1 5 2 8 1 3 5 187 1 3 2 640 1 10 0 1 4 1 3 1 5 1 3 1 6 0 5 1 3 1 5 1 5 0 3 0 6 7 4 3 4 1 2 5 26 1 6 4 30 1 2 4 1000 1 3 1 445 1 5 6 92 1 1 2 29 1 10 0 1 4 1 5 0 1 0 5 0 3 1 4 1 2 1 4 1 3 1 4 1 6 7 4 2 87 1 2 5 23 1 1 2 16 1 4 3 24 1 6 4 4 1...
output:
286 97 284 97 0 284 97 284 0 0 177 0 0 0 181 177 29 177 181 177 0 103 103 0 127 127 0 0 103 127
result:
ok 30 lines
Test #3:
score: 5
Accepted
time: 77ms
memory: 153924kb
input:
3 50 121 37 15 454 1 23 5 386 1 28 38 894 1 17 31 8 1 38 43 387 1 5 43 308 1 18 39 15 1 34 9 506 1 34 49 15 1 50 3 119 1 13 27 483 1 45 17 835 1 25 2 966 1 24 30 71 1 37 19 28 1 43 7 905 1 10 4 107 1 37 35 416 1 20 13 18 1 47 20 16 1 6 24 116 1 12 47 974 1 48 41 809 1 10 47 17 1 9 42 13 1 16 36 892 ...
output:
1526 1503 1503 1466 1369 1665 1650 1650 0 0 497 0 1402 1671 1401 1379 1451 1646 1650 1671 1646 1365 1646 1215 0 1413 1330 1483 1665 0 1646 0 1402 0 1650 1215 0 1650 1357 1246 1650 1215 1264 1330 1425 1646 1526 1665 1526 1665 0 1482 1646 0 1466 808 1646 0 1375 1646 1521 1291 1665 500 1526 1665 1671 1...
result:
ok 300 lines
Test #4:
score: 5
Accepted
time: 83ms
memory: 153928kb
input:
3 100 259 62 44 8 1 26 69 30 1 37 34 280 1 36 8 80 1 12 47 2 1 78 98 17 1 35 16 914 1 91 75 7 1 80 76 943 1 93 45 3 1 51 100 518 1 26 59 146 1 76 73 231 1 23 73 11 1 64 10 858 1 51 54 7 1 51 86 696 1 59 40 150 1 17 20 64 1 60 43 16 1 78 7 926 1 46 2 440 1 26 82 922 1 32 12 46 1 31 72 756 1 64 70 876...
output:
1007 944 739 905 1286 1018 1001 1260 1262 1035 1262 905 993 1015 1266 1281 779 992 460 1281 739 759 1252 795 0 992 1004 1281 1260 1286 1286 1247 1266 1252 739 1262 0 0 1260 1262 0 836 1001 1053 1012 455 1028 1286 1281 0 1004 1262 1286 992 992 1036 1016 895 930 1007 1286 1281 1286 1063 1252 1004 985 ...
result:
ok 600 lines
Test #5:
score: 5
Accepted
time: 70ms
memory: 154176kb
input:
3 1403 4000 659 1257 556 1 428 883 77 1 398 429 623 1 934 998 916 1 408 1318 15 1 595 299 249 1 1243 483 668 1 335 1229 560 1 1357 697 607 1 91 555 4 1 131 508 847 1 591 254 219 1 1004 1319 11 1 209 78 299 1 328 532 21 1 1001 1215 12 1 768 981 762 1 1316 254 126 1 584 1338 583 1 125 869 29 1 745 330...
output:
4637 4318 4318 3466 3860 4318 4171 3728 1452 2474 4098 3412 4033 0 4552 3755 4637 4222 4222 4098 3702 3567 0 3961 0 4249 3738 0 2807 4108 3542 3399 3793 3942 0 3876 2806 0 3779 4108 3414 4108 3627 3648 2792 0 3961 2948 0 4015 4222 4108 1655 0 4108 3953 3658 3890 0 3690 3942 3660 3736 4015 4108 3937 ...
result:
ok 6000 lines
Test #6:
score: 5
Accepted
time: 1360ms
memory: 183160kb
input:
3 134023 400000 106936 27428 617 1 31553 30342 971 1 19790 1355 127 1 49584 42179 26 1 28910 65772 18 1 48591 55180 17 1 4998 88813 195 1 82176 121958 759 1 21077 25885 341 1 120910 35270 883 1 27537 33116 20 1 78351 18357 6 1 101608 66216 426 1 30213 43293 998 1 37468 49783 586 1 103877 17557 19 1 ...
output:
31014 31770 29737 32596 31117 0 31268 32495 30147 32871 30756 31980 0 31998 32693 26033 32417 9337 31438 32177 32641 31414 31804 33026 32575 27777 0 26698 32652 31867 32450 32271 32652 25847 32652 32302 28402 32177 32302 32197 31661 31799 31713 31814 32107 27295 32565 32250 31712 31125 0 32624 30224...
result:
ok 300000 lines
Test #7:
score: 5
Accepted
time: 78ms
memory: 154024kb
input:
3 1500 1499 1263 1264 197 832549205 1407 1408 695 932716365 1146 1147 40 750669441 1386 1387 484 927439941 1178 1179 83 778216556 241 242 317 128333415 1189 1190 759 779845130 1447 1448 288 967694365 1041 1042 783 693510784 913 914 798 601420727 1359 1360 840 901837603 1225 1226 191 800290452 998 99...
output:
149260 464744 481512 389212 287741 237840 59609 156654 208739 107460 565246 334656 43465 456781 367213 544844 636763 109052 55085 595734 355225 256368 328550 69613 315734 255641 36508 628714 690980 222717 55085 675231 499689 124300 234411 642017 179131 115720 326655 500542 138109 288098 524140 55620...
result:
ok 6000 lines
Test #8:
score: 5
Accepted
time: 76ms
memory: 154188kb
input:
3 1500 1499 214 215 746 103777342 1305 1306 809 863481069 780 781 193 489096281 1380 1381 333 918631020 1299 1300 53 866441833 981 982 823 625528911 606 607 551 354810974 345 346 910 191333196 1475 1476 254 977255759 227 228 736 118721990 1378 1379 137 916242486 55 56 168 28186639 1338 1339 981 8937...
output:
159954 339343 458570 458570 203878 580405 621372 93231 58933 175182 110766 662839 79318 248759 391633 98798 29686 79318 430391 119721 490097 329847 642364 1382 203878 462322 704124 276766 453424 556535 557525 557525 672166 454002 747531 342380 616501 438728 250858 632594 222786 545457 240393 347834 ...
result:
ok 6000 lines
Test #9:
score: 5
Accepted
time: 61ms
memory: 154020kb
input:
3 1500 1499 186 187 314 94742289 75 76 261 39423111 1034 1035 125 648876320 1428 1429 832 941472266 1181 1182 504 752620972 342 343 486 178026302 440 441 192 240994251 1431 1432 552 945810062 1229 1230 159 790119569 1194 1195 565 761837664 113 114 256 55257526 636 637 238 352763203 1213 1214 756 781...
output:
569689 312985 696132 60974 688719 393018 501235 488432 614064 271703 137383 250965 154888 211437 738940 518300 108142 57565 443490 192843 526972 85447 404013 345230 485990 665361 401934 391877 702266 638461 87637 493465 152001 6298 716651 102922 171244 398821 332876 377487 139973 349964 583015 58074...
result:
ok 6000 lines
Test #10:
score: 5
Accepted
time: 1088ms
memory: 170988kb
input:
3 200000 199999 168039 12763 765 279320236 183939 16430 198 6881839 122193 47956 163 21807713 67770 169599 261 994936289 74818 123071 837 825259015 150448 32275 987 90179474 155426 115119 567 807410643 143919 114116 968 915726797 92951 9762 998 671084406 150297 117878 862 107998837 91701 134269 653 ...
output:
65779635 80678744 63515461 86227552 74769861 52122522 450819 89491882 86315837 5026098 38465492 54922440 81958976 80460791 93084090 4505293 11390406 62027241 43923829 80153947 1425999 41017046 89392328 34047372 39431143 14680982 43791379 60145739 13719811 77415622 85100892 91377866 87387701 24532016...
result:
ok 300000 lines
Test #11:
score: 5
Accepted
time: 1139ms
memory: 170988kb
input:
3 200000 199999 176394 15779 785 127180026 118840 52233 628 69674288 1971 33381 302 757977279 72869 125444 355 183017412 104923 147605 520 839789866 124478 39387 865 582607027 155179 30904 563 287043678 62654 32772 741 221773407 175009 23990 438 117663422 177376 176873 136 848504696 57250 16505 54 8...
output:
27739808 89958497 74839886 41091196 40434595 81500937 37903685 94813799 88772134 64079457 7227617 82050147 53862990 27122905 3702939 66860503 19384105 63627827 85272577 78259960 51490641 87930052 70169237 64794654 4108403 3063959 66258350 22170687 53361620 56815550 92326958 76943918 5643824 61492738...
result:
ok 300000 lines
Test #12:
score: 5
Accepted
time: 1550ms
memory: 184516kb
input:
3 134023 400000 67041 63272 992 180592857 41473 75825 108 301222188 114213 118633 12 580124132 20125 31290 30 519396153 90723 84443 189 316168642 84070 23184 683 111413871 112204 69103 389 388055662 115520 39583 310 273512441 105629 49771 973 81918254 112276 117987 26 749496507 121962 108299 838 256...
output:
0 0 0 0 32038 0 0 28793 33179 32743 0 0 32249 0 0 0 0 11485 23537 29633 0 0 23977 33163 32754 0 32542 32596 33179 9635 0 21084 0 33521 0 0 0 15299 0 16912 33110 33179 0 15557 33214 32824 32779 31244 0 0 32507 33110 0 33110 0 0 32919 33110 0 32830 0 0 0 0 0 0 33179 32463 0 0 0 0 0 0 0 0 33110 0 25266...
result:
ok 300000 lines
Test #13:
score: 5
Accepted
time: 1539ms
memory: 184684kb
input:
3 134023 400000 58760 3502 768 215875099 107385 86405 15 527479997 132742 112734 946 444077360 17162 37315 564 392834909 112439 74725 25 747453202 132349 88516 327 84395270 73108 131771 99 18974938 109915 50777 727 263001501 62336 37521 630 149446391 41770 2858 621 21949981 130072 108091 323 4229302...
output:
0 23801 32156 21200 16692 32317 16404 32031 16386 10568 31863 24877 3114 0 0 32444 0 12954 32551 32436 32317 0 32098 0 0 0 0 32272 0 0 0 0 32018 19115 0 32001 0 31863 0 0 10177 0 0 32551 7618 0 32566 0 0 32101 32264 21200 32264 0 31812 0 31824 19647 32436 32318 0 0 31965 0 0 0 0 27708 27186 0 32219 ...
result:
ok 300000 lines
Test #14:
score: 5
Accepted
time: 1546ms
memory: 184524kb
input:
3 134023 400000 15491 25039 962 444781241 43770 90154 968 416678205 19896 66733 917 208667421 15023 2102 692 444508565 74033 113231 3 504471242 94078 25801 8 624427171 102961 120670 491 241484370 78528 3616 27 586135212 107319 5083 876 40723199 28998 77345 384 304581393 116304 47118 591 153577459 81...
output:
11811 0 0 0 0 0 0 0 31726 32654 0 0 32091 0 25154 0 0 32174 32253 27468 32506 0 0 0 23388 0 28400 0 0 32072 0 0 0 31788 20395 0 32174 6679 0 32099 8633 0 32253 29108 0 26922 0 0 31977 32304 15748 0 0 0 17651 0 21759 6341 0 0 30439 0 32282 9284 31696 3882 31834 31919 0 31722 32286 32654 26619 32174 3...
result:
ok 300000 lines
Test #15:
score: 5
Accepted
time: 83ms
memory: 154340kb
input:
3 1403 4000 63 230 9 792459870 250 10 521 435710193 186 75 483 41567023 185 1006 566 219013432 1148 740 142 41210356 486 1050 48 488430239 1218 60 5 939467812 369 1002 373 377523109 877 1206 29 656561482 980 659 81 342719745 544 17 958 234525425 880 1010 85 63567532 579 238 394 313448548 631 102 8 6...
output:
4658 3980 3580 0 0 3866 4596 0 0 0 4692 0 4765 0 0 3523 0 0 5002 0 0 0 0 0 0 0 0 0 0 0 4213 0 3146 0 0 5330 0 0 3029 0 4667 0 0 0 3779 5002 4911 0 0 0 4915 5330 3184 3924 4665 0 4911 0 1069 0 4692 5222 3712 4596 0 0 0 5269 4834 0 5002 0 4692 0 5079 0 0 4915 4054 0 4803 0 4213 4911 0 4332 4739 0 4596...
result:
ok 6000 lines
Test #16:
score: 5
Accepted
time: 78ms
memory: 154352kb
input:
3 1403 4000 65 36 108 94567299 497 73 930 399127210 814 128 811 105804086 300 479 8 925063872 644 583 749 61035098 769 1221 9 756940473 129 1005 650 421450316 434 116 793 38919578 420 253 20 693812030 313 170 12 810090183 1296 689 837 148940335 32 491 5 909075814 720 1358 30 797814306 661 572 954 35...
output:
5416 0 0 0 2894 0 0 0 5135 0 0 4917 0 4849 0 5229 0 4703 0 4849 5448 0 4703 0 0 0 2884 0 0 0 0 0 0 0 4931 5416 0 0 0 5442 0 4982 5503 5029 0 0 0 0 0 0 0 1967 5510 0 0 0 0 0 4856 5134 5135 3546 4703 0 0 4227 0 3667 5083 0 5154 0 5416 0 5154 0 4931 0 3715 5135 0 2932 0 0 5315 0 0 0 4672 5229 0 0 4014 ...
result:
ok 6000 lines
Test #17:
score: 5
Accepted
time: 1496ms
memory: 184644kb
input:
3 134023 400000 124828 37415 961 94076145 12469 128238 20 641194816 130567 15737 167 118907136 131297 6336 25 524919668 116982 130433 24 756819767 33316 74251 964 98831248 67280 6664 493 47288237 119344 53718 25 275115234 123245 128903 701 193512252 67851 82761 537 434699228 105776 133640 27 7409207...
output:
0 30691 29617 2222 32343 0 0 28179 0 0 0 0 6198 32314 32444 29779 0 0 0 0 25794 0 11709 0 32159 32200 32347 0 0 0 10133 23825 32589 27915 0 32200 28733 0 0 0 32776 32589 0 32432 14246 0 0 0 0 32325 29700 0 0 0 0 32347 0 0 32334 32421 0 0 0 27370 0 0 0 0 16208 0 32999 31749 32578 31196 0 32347 11718 ...
result:
ok 300000 lines
Test #18:
score: 5
Accepted
time: 1550ms
memory: 184548kb
input:
3 134023 400000 93897 30157 297 268792428 132559 55246 25 703055243 78340 95366 168 238768162 14465 13469 535 64125745 18273 112312 807 440189389 47009 122943 109 38388604 132558 29279 424 51116970 7442 50269 90 474483522 77415 104844 996 533591796 65098 57707 23 806817064 20920 120036 439 419244143...
output:
0 27460 0 0 0 22533 23617 0 0 32985 0 33117 0 11343 0 33092 7266 0 26670 29528 0 8425 32658 19908 32658 0 0 0 12939 10085 0 19388 32807 0 0 0 0 0 0 0 33232 0 0 33098 0 0 0 0 30860 32892 23536 0 33415 32985 0 31706 26670 32101 0 31715 0 28821 33775 32686 32829 22024 0 10741 0 0 0 33869 32658 33287 0 ...
result:
ok 300000 lines
Test #19:
score: 5
Accepted
time: 2250ms
memory: 184640kb
input:
3 134023 400000 8769 5728 809 19387679 57063 91233 797 253655114 130290 72440 967 32496257 91843 24946 657 501122161 49847 43516 108 85279737 9697 18896 695 273697557 46300 88649 364 14955048 20408 46673 788 79075025 105581 10860 9 806715014 35442 17634 946 64078166 74381 121008 17 680814138 33256 6...
output:
0 32798 32668 32591 0 0 28226 0 0 0 33669 0 0 0 0 0 0 0 20127 33126 14909 33577 33552 0 32990 0 0 0 0 12484 0 12868 28263 0 0 15117 32595 32732 0 0 23781 0 32963 0 32742 7251 0 29789 21158 0 33165 32958 32302 0 17344 0 0 0 8231 0 33816 0 33323 32705 0 0 32731 0 25503 0 32490 20268 0 30236 32731 3242...
result:
ok 1200000 lines
Test #20:
score: 5
Accepted
time: 2245ms
memory: 184684kb
input:
3 134023 400000 102887 57011 25 621065092 104930 92183 31 572560306 118658 64299 848 501142203 131931 87158 65 200398712 132887 33804 15 654384648 46738 88508 15 616094154 113013 63932 174 188235708 51888 86629 17 551871892 12748 98037 218 210399397 85016 84392 818 377250424 126145 20672 857 1336467...
output:
0 0 0 0 5175 11407 0 33296 33025 32977 26332 0 33433 0 0 0 32906 0 32894 33433 0 33128 0 32346 0 0 12845 33180 33576 0 32852 0 21913 0 33251 22015 33233 33233 0 32906 32716 8498 0 0 33109 0 0 0 0 15322 32427 32986 9676 0 32592 0 25916 32959 33587 32741 0 25637 0 0 12540 26719 0 33080 31887 0 14952 3...
result:
ok 1200000 lines
Extra Test:
score: 0
Extra Test Passed