QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#487007 | #5439. Meet in the Middle | luanyanjia | WA | 63ms | 58228kb | C++14 | 4.0kb | 2024-07-22 15:06:07 | 2024-07-22 15:06:07 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int N=1e5+5;
int n,q;
#define MIN(x,y) dis[x]<dis[y]?x:y
namespace T2{
int fst[N],nxt[N<<1],v[N<<1],w[N<<1],idx;
int lg[N<<1],st[19][N<<1],fir[N],dep[N],dis[N],cnt;
inline void Add(int a,int b,int c){
v[idx]=b,w[idx]=c;
nxt[idx]=fst[a];fst[a]=idx++;
}
void DFS(int x,int fa){
st[0][++cnt]=x,fir[x]=cnt;
for(int i=fst[x];~i;i=nxt[i]){
int y=v[i];
if(y==fa)continue;
dep[y]=dep[x]+w[i];
dis[y]=dis[x]+1;
DFS(y,x);
st[0][++cnt]=x;
}
}
inline int LCA(int x,int y){
x=fir[x],y=fir[y];if(x>y)swap(x,y);int k=lg[y-x+1];
return MIN(st[k][x],st[k][y-(1<<k)+1]);
}
inline void Prework(){
dis[1]=0;DFS(1,1);
for(int i=2,j=1;i<=2*n;i++){if((1<<(j+1))<=i)++j;lg[i]=j;}
for(int len=1,j=1;len<cnt;len<<=1,j++)
for(int i=1;i+len<=cnt;i++)
st[j][i]=MIN(st[j-1][i],st[j-1][i+len]);
}
inline int Dist(int x,int y){
return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
}
namespace T1{
int fst[N],nxt[N<<1],v[N<<1],w[N<<1],idx;
int sz[N],dep[N],dfn[N],cnt,ans[N],fdfn[N];
vector<pair<int,int> >vc[N];
inline void Add(int a,int b,int c){
v[idx]=b,w[idx]=c;
nxt[idx]=fst[a];fst[a]=idx++;
}
namespace BIT{
int t[N];
inline void Add(int x,int v){while(x<=n)t[x]+=v,x+=x&-x;}
inline int Query(int x){int ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
}
inline int Dist(int x,int y){
if(x==y)return 0;
return T2::Dist(x,y)+BIT::Query(dfn[x])+BIT::Query(dfn[y]);}
namespace SGT{
struct node{
int x,y,dis;
node(){x=0,y=0,dis=0;}
node(int _x,int _y){x=_x,y=_y,dis=Dist(x,y);}
bool friend operator<(const node &a,const node &b){return a.dis<b.dis;}
node friend operator+(node a,node b){
a.dis=Dist(a.x,a.y);
b.dis=Dist(b.x,b.y);
node res=max(a,b);
res=max(res,max(node(a.x,b.x),node(a.x,b.y)));
res=max(res,max(node(a.y,b.x),node(a.y,b.y)));
return res;
}
}t[N<<2];
void Build(int i,int l,int r){
if(l==r){return t[i]=node(fdfn[l],fdfn[l]),void();}
int mid=(l+r)>>1;
Build(i*2,l,mid);
Build(i*2+1,mid+1,r);
t[i]=t[i*2]+t[i*2+1];
}
void Update(int i,int l,int r,int x){
if(l==r)return ;
int mid=(l+r)>>1;
if(x<=mid)Update(i*2,l,mid,x);
else Update(i*2+1,mid+1,r,x);
t[i]=t[i*2]+t[i*2+1];
}
}
void DFS(int x,int fa){
sz[x]=1;dfn[x]=++cnt;fdfn[cnt]=x;
BIT::Add(dfn[x],dep[x]);BIT::Add(dfn[x]+1,-dep[x]);
for(int i=fst[x];~i;i=nxt[i]){
int y=v[i];
if(y==fa)continue;
dep[y]=dep[x]+w[i];
DFS(y,x);
sz[x]+=sz[y];
}
}
void Solve(int x,int fa){
for(auto p:vc[x])ans[p.second]=max(Dist(SGT::t[1].x,p.first),Dist(SGT::t[1].y,p.first))-BIT::Query(dfn[p.first]);
for(int i=fst[x];~i;i=nxt[i]){
int y=v[i];
if(y==fa)continue;
BIT::Add(dfn[y],-w[i]);BIT::Add(dfn[y]+sz[y],w[i]);
BIT::Add(1,w[i]);BIT::Add(dfn[y],-w[i]);
BIT::Add(dfn[y]+sz[y],w[i]);BIT::Add(n+1,-w[i]);
SGT::Update(1,1,n,dfn[y]),SGT::Update(1,1,n,dfn[y]+sz[y]-1);
Solve(y,x);
BIT::Add(dfn[y],w[i]);BIT::Add(dfn[y]+sz[y],-w[i]);
BIT::Add(1,-w[i]);BIT::Add(dfn[y],w[i]);
BIT::Add(dfn[y]+sz[y],-w[i]);BIT::Add(n+1,w[i]);
SGT::Update(1,1,n,dfn[y]),SGT::Update(1,1,n,dfn[y]+sz[y]-1);
}
}
inline void Main(){
memset(fst,-1,sizeof fst);
memset(T2::fst,-1,sizeof T2::fst);
rd(n,q);
for(int i=1;i<n;i++){
int x,y,z;rd(x,y,z);
Add(x,y,z);Add(y,x,z);
}
for(int i=1;i<n;i++){
int x,y,z;rd(x,y,z);
T2::Add(x,y,z);T2::Add(y,x,z);
}
T2::Prework();
for(int i=1;i<=q;i++){
int a,b;rd(a,b);
vc[a].push_back(make_pair(b,i));
}
DFS(1,1);
SGT::Build(1,1,n);
Solve(1,1);
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
}
}
signed main(){
T1::Main();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 35524kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
6 4 5 3
result:
ok 4 number(s): "6 4 5 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 33604kb
input:
2 1 1 2 1 1 2 1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 34128kb
input:
2 1 1 2 1 1 2 1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 38ms
memory: 56644kb
input:
10000 50000 8101 5996 108427744 5996 7605 870838849 5996 5599 603303696 8101 3006 339377417 8101 6463 442516687 6463 5560 109174079 5560 4063 127596224 3006 1682 947915262 5996 1986 130416311 6463 5455 279771516 6463 2634 516688796 4063 3034 217886863 7605 5092 742375061 5599 2266 193804402 5092 140...
output:
647838384844 626539793176 514273941704 637066393138 472546379596 645842915960 641537859258 573604504956 644081575470 803875451466 674370549986 734764046916 744862815441 763778393516 553499885160 526743824759 610373719514 689550247042 549161302822 726811438160 653134244120 666761991962 701575393972 6...
result:
ok 50000 numbers
Test #5:
score: 0
Accepted
time: 45ms
memory: 55932kb
input:
10000 50000 5314 8843 137901358 5314 4153 459134340 5314 8667 933926892 4153 6504 330487798 4153 8880 750362377 4153 5990 874275912 4153 546 563436331 5990 6216 902348875 8843 3101 669215553 6216 8138 732343176 8667 8675 581114294 6504 7416 127778711 546 4239 282695908 6504 9455 549237168 5314 8340 ...
output:
464564968641 331633000004 565299667784 484694871646 570451097836 417492802442 372302349684 638725688107 386235986078 355738655551 462027769535 558485994764 524714144289 450157947013 432701214095 494566741391 529031758638 637683369382 415646847933 344894296260 390294136162 527685175763 575151290175 3...
result:
ok 50000 numbers
Test #6:
score: 0
Accepted
time: 47ms
memory: 57936kb
input:
10000 50000 2808 2490 757309564 2808 9601 312271047 2808 4046 119325897 2808 4894 466822371 4894 1507 498399554 2490 5982 84088145 9601 1251 149019541 2808 6681 416590999 2808 6583 357757899 1251 3192 889947539 6583 9762 350572496 6681 22 597479070 5982 8744 263208242 8744 5281 49894126 1507 8806 30...
output:
1501072697023 2058806276380 2017086500812 2044250452467 1543567245539 1695101693278 1765462307870 2576423082091 2302805133490 2090282734929 2375783476943 1954788661090 2056530503168 2453153202726 1978028047409 2106220371212 2210163378358 2015714406862 1555876274751 2122832986951 2102262624814 169085...
result:
ok 50000 numbers
Test #7:
score: 0
Accepted
time: 63ms
memory: 58228kb
input:
10000 50000 4064 7188 81750473 7188 8466 310631946 8466 2276 154981798 2276 7347 162965456 7188 464 806245243 464 2250 849189978 8466 641 734602751 8466 9246 225800419 4064 5267 191524437 2276 5292 192776095 2276 9036 414997994 9246 5470 362146726 2250 473 98496385 4064 7726 700294189 473 9503 42824...
output:
3589143478793 5241855728342 3397106617685 3432843859461 4544481241003 3649934075137 3020107625030 3297847713344 3894730366667 3030559097282 4824131552194 4821302024170 4471510161493 3291683748595 4954639576578 2961243269520 3659899432127 3421183608349 5262802614761 4408705330639 5203984107670 500158...
result:
ok 50000 numbers
Test #8:
score: 0
Accepted
time: 46ms
memory: 56832kb
input:
10000 50000 8676 4714 406191383 8676 5040 603960140 5040 9715 635348098 4714 9483 594267326 9483 5451 409058229 8676 8913 909259106 9715 1399 320185961 9715 4857 180234031 4714 8888 585099487 5040 1244 645347755 5451 7736 479423492 9483 1038 272038574 1399 3970 638817231 8888 3314 55726955 8888 2295...
output:
447424387353 491327570749 614052040822 384218910068 429859933145 356174725430 609432604118 465420084327 472632020898 382647454960 343751681021 441874503695 463199624732 610943875286 563031986601 566780763247 346991783125 601234775562 619765985074 357316826763 495874578271 526431260851 331681020073 4...
result:
ok 50000 numbers
Test #9:
score: 0
Accepted
time: 44ms
memory: 56492kb
input:
10000 50000 30 8765 730632293 8765 4245 897288335 30 4974 965971295 4974 9464 585377707 9464 744 157095406 744 6387 969328235 744 235 905769171 744 912 989443452 744 1341 273641834 744 9933 802952118 4974 8348 248881694 8765 9127 36706230 912 6136 324362270 4974 8517 411159721 8348 1941 672019024 94...
output:
260285187513 334448828465 448073136303 349497881882 360969017248 402078622370 390257279014 308648100196 320994952264 289449337583 393159064851 453034865550 283828471834 446349617896 380894281657 408838602752 363824724502 420964873388 362606539223 391080537186 304570333981 245848347318 310973758007 3...
result:
ok 50000 numbers
Test #10:
score: 0
Accepted
time: 45ms
memory: 56640kb
input:
10000 50000 2152 8278 350040498 2152 3058 895649234 3058 2264 151370300 8278 6118 576488088 8278 7313 464941095 3058 6966 884173172 6966 9779 786319677 9779 9796 943877064 6118 929 517473780 6118 2651 550491074 7313 662 313307192 7313 8043 506406589 7313 1698 864683116 6118 5060 766592488 6966 1903 ...
output:
652477746679 597325264627 539318490039 597048004752 421646977029 649309274459 506349020540 429554460108 462828559625 593933122751 543584884281 652286846854 654020863570 717938057245 431237695994 601883634488 731084254857 588856926225 399175030875 575410680840 526320427336 494819850806 529049784844 5...
result:
ok 50000 numbers
Test #11:
score: 0
Accepted
time: 47ms
memory: 57852kb
input:
10000 50000 7747 7582 379514112 7582 4607 188977429 7582 5317 187026200 7747 8600 712822661 8600 4262 212978273 7747 827 649275004 827 8014 76935591 7747 6641 753086484 7582 8582 206016126 8014 8460 708095438 8014 9211 377732689 8582 4450 416298437 827 9208 699971259 9208 6823 416992550 8582 186 770...
output:
746737735180 498470031337 630778245801 714337715073 566315588400 809241414480 668680437815 575990359534 612421079786 631355089285 534254563162 566879359756 667087033615 650377712872 669587743650 611030906118 593248384501 735077133684 585253655611 595113935966 519628983099 603281284099 529926712130 5...
result:
ok 50000 numbers
Test #12:
score: 0
Accepted
time: 49ms
memory: 57888kb
input:
10000 50000 3472 122 628742395 3472 3867 379635964 3867 1902 749838600 3867 7438 305533780 122 6633 278565996 122 1661 208291710 7438 3819 677928429 1902 7425 657683150 1661 5239 676247552 1902 2756 448261111 7438 7365 97063037 3819 6763 371040229 6633 8865 356148629 6763 5581 863369674 6633 1551 46...
output:
608697605604 482134269787 577721966634 628074778968 445000575297 484814952220 511586460160 374153126368 469519128844 602443844531 619658782918 385417337773 345965815878 620132139546 609655051154 537845187251 622122602447 436588599524 531403283302 587074749895 441226010189 421564270566 406700017163 5...
result:
ok 50000 numbers
Test #13:
score: 0
Accepted
time: 44ms
memory: 56864kb
input:
10000 50000 1160 9231 559787863 9231 4770 299521320 9231 9192 876373929 4770 3107 498755345 1160 5830 724175215 3107 9464 281278611 5830 3611 15139105 4770 7601 642740087 9464 910 538577221 9464 8134 554493711 7601 5225 259081456 9192 4493 741155925 5225 7756 789054604 5225 9044 160953940 7601 6104 ...
output:
44163199908 36544889589 45890256673 36776414195 37333219129 39650732470 43389306319 38148496085 42684423989 37470526473 42398992970 40710607327 42271798904 40981602830 42083787825 41411720865 39511748870 39133821656 42107800923 40131700757 38159799832 39161288828 43514631246 38415055107 37202416831 ...
result:
ok 50000 numbers
Test #14:
score: 0
Accepted
time: 47ms
memory: 56944kb
input:
10000 50000 4350 9200 67344024 4350 3516 652031480 9200 9124 852386373 3516 3291 174252855 9124 6162 531615996 3516 3512 591430394 9124 1486 34243545 9200 6098 389999654 6162 3831 371706900 3512 4570 438513693 6162 312 142582166 3512 2336 718583156 4570 7409 610288335 2336 7420 1537001 7420 7842 827...
output:
1281632463885 1210271183079 1237017380491 895833426340 1283280064455 942224768023 892689065199 798697911014 751216197267 758455784557 1141824774281 820909870575 1014030803803 957938689064 1219651503682 771983156874 1178424399518 788435609430 1077287342681 1093062283731 946704599027 893784573061 1275...
result:
ok 50000 numbers
Test #15:
score: 0
Accepted
time: 46ms
memory: 57068kb
input:
10000 50000 9863 2086 776561351 2086 3631 126823773 9863 3392 474209454 3631 9001 149307847 9001 9522 263109666 3392 5761 187746709 9001 3767 870963783 3631 3788 726791 9522 4896 223271095 5761 1160 858678197 5761 543 58975325 3767 9995 875487770 1160 7361 101433507 4896 8325 954009430 8325 3351 894...
output:
3639977233620 3530907756332 2675379129344 4448022048643 2573190330483 4499414931784 3266309481456 3096703943537 2626858162069 3705044120135 3214988142418 3607045075418 2855013843207 4100248201012 2944552371007 3467914981358 4012578656847 4011860831951 5010047454262 4258401519515 4612650790910 498761...
result:
ok 50000 numbers
Test #16:
score: 0
Accepted
time: 48ms
memory: 56560kb
input:
10000 50000 4049 3217 948325921 4049 5052 335875847 5052 1077 805501667 1077 5617 791326096 3217 6795 341938001 1077 1687 296345105 6795 4846 592548551 5052 605 480047794 1687 1641 278347154 5617 4357 204297995 605 314 916793543 605 2278 379707422 2278 1593 345641808 1687 8644 903411591 1593 4760 76...
output:
22692370014 26671995767 23223650964 25037938894 24746389474 23697688458 23151041959 23816855885 23838338206 24834553266 26196330065 24533366219 26308807100 27248674922 25552842773 26570165114 22870797629 23557706389 26691697989 25265417363 24630757806 26415052596 25655335960 24347193370 26001962880 ...
result:
ok 50000 numbers
Test #17:
score: 0
Accepted
time: 48ms
memory: 56920kb
input:
10000 50000 6523 4998 683131495 4998 935 871371995 6523 9691 163318078 9691 8916 578451344 9691 9874 961103371 8916 685 208189809 685 8871 368173207 8916 6734 382636596 685 5383 69823504 8871 5902 340803834 4998 587 182084912 935 8296 327702300 5383 4787 216764061 5383 2603 471182122 587 7372 923681...
output:
24346279878 24159724129 19056689759 21329886740 23717511632 21152471010 22089148390 19124036591 20347315967 22739779159 21892965420 21733073800 20715327790 19193604096 20429859569 23181805930 23345539065 21847491691 20610795206 20970932375 20066420900 25367510483 25843830881 20702116769 20515076455 ...
result:
ok 50000 numbers
Test #18:
score: 0
Accepted
time: 50ms
memory: 56484kb
input:
10000 50000 8136 1635 842124659 8136 2446 96949099 1635 3483 867846492 1635 7944 589014022 2446 207 229225727 7944 1395 875428514 7944 312 711917988 3483 4069 668199427 4069 2891 305479784 4069 4426 368431680 3483 1607 247762956 1395 7960 213299897 1607 6273 261862409 207 8056 602952 7960 2331 89834...
output:
221805361345 344330244834 301417460297 196121116177 222185764926 269532557170 198254727612 342514611011 271623778301 249627562926 352800786311 318085376117 259654080926 283228181375 306204031853 331174503459 236933657251 189132469039 318214396178 200056424582 246470661905 244719493308 274008065442 3...
result:
ok 50000 numbers
Test #19:
score: 0
Accepted
time: 41ms
memory: 56552kb
input:
10000 50000 334 352 60206968 352 305 837992380 305 8581 842844833 334 8942 264051201 352 6003 382159029 8942 5537 30427164 8581 5969 913354403 6003 905 682266733 5969 1403 303476090 5969 7464 32917776 6003 2070 859897901 2070 3467 234241345 3467 8698 320427414 8581 7873 37110524 1403 8517 185370301 ...
output:
581969194691 514453676470 390553242144 398767185182 396307411698 584378802405 654841477333 639529239848 655418442247 730832203542 400197481561 640310612327 591358565895 582685012783 649766947177 653842132618 655829106256 632258804246 648019844537 634680579467 592078061031 629280869021 403624822082 6...
result:
ok 50000 numbers
Test #20:
score: 0
Accepted
time: 47ms
memory: 57852kb
input:
10000 50000 2912 1663 153488050 1663 350 727308826 350 5343 783761508 5343 4104 46303186 4104 4018 493469519 4018 7659 338930839 7659 7533 245268135 7533 7193 290715498 7193 1634 377621959 1634 4211 94097273 4211 8929 767914581 8929 9758 539944169 9758 5342 960382115 5342 9418 972428758 9418 7598 33...
output:
1190970395145 1233073741726 1371353640922 1331841332961 1378285681669 1293803818492 1686098601566 1618705136059 1050063891251 1662210882776 1448886276816 1832119288597 1763213206091 1156731099316 1524816455948 1335795776622 1633864615670 1516179736541 1415679696558 1438625445786 1615887718882 189147...
result:
ok 50000 numbers
Test #21:
score: 0
Accepted
time: 48ms
memory: 54908kb
input:
10000 50000 1582 4135 838497045 4135 3442 702336909 3442 375 533282097 375 7146 882775805 7146 7807 86813140 7807 2263 859334122 2263 4883 392374535 4883 764 848075477 764 8723 793741265 8723 7925 470473887 7925 9112 861905098 9112 9330 805905723 9330 1010 229417453 1010 1029 642466213 1029 9335 709...
output:
1127922564814 1281785466573 973255728311 1332854046538 1161797930892 807045830722 1425252079799 1039233881246 980497481096 1216098061633 1476646339263 1533948111753 1212122907197 1332660079468 955677153525 1259815716640 1086329148065 909766639115 1338471739010 939166362772 1340194437028 104118973954...
result:
ok 50000 numbers
Test #22:
score: 0
Accepted
time: 43ms
memory: 56996kb
input:
10000 50000 4451 9061 799400506 9061 1178 240231790 1178 5175 327625710 5175 2065 504597872 2065 7467 395771348 7467 4338 90256163 4338 7909 39263862 7909 6047 959079033 6047 4521 939635800 4521 1781 570412122 1781 7114 41842045 7114 9567 538188744 9567 6660 479347504 6660 5084 475415876 5084 7759 2...
output:
2612835250496 2316736477624 2309048258185 2157172758992 2377745518491 2409756133919 2272336592611 2053957710271 2157940052734 2055432584295 2389859879140 2584767884856 2084451671595 2691085170630 2552358316415 2117293003432 2601352641000 2038665655976 2262026232194 2883248280386 1930369024422 263238...
result:
ok 50000 numbers
Test #23:
score: 0
Accepted
time: 42ms
memory: 57268kb
input:
10000 50000 2406 3956 170266249 3956 4278 617152977 4278 9621 802573824 9621 7235 499787802 7235 7940 556199678 7940 5712 268451785 5712 8272 380260179 8272 9454 312873112 9454 37 928734978 37 8494 918251253 8494 2702 909777424 2702 2897 511382005 2897 2473 650541982 2473 8739 540826760 8739 1318 57...
output:
3688449984397 3506033630019 3926985837670 4985948471880 5772244887821 5602256960659 4730388411655 5141144647115 3882620480043 5244011267795 6180288345261 4561619240491 4424170939376 4452089542635 5272350745707 5067654692782 4316283105320 6103750854868 4951431868818 4953378642955 4369957992172 502862...
result:
ok 50000 numbers
Test #24:
score: 0
Accepted
time: 40ms
memory: 56996kb
input:
10000 50000 9430 4862 90250453 4862 5092 294400353 5092 2612 484501098 2612 8881 932929771 8881 7630 665290950 7630 6880 197581047 6880 6106 295913729 6106 3182 888334009 3182 2764 687623650 2764 7330 955188014 7330 5888 105599141 5888 5128 827517314 5128 9673 626535422 9673 9500 218347441 9500 4501...
output:
1442822272365 1249968437919 1368459443408 925425673049 1371626107255 1501244260337 1123727805409 1434888268789 1537663432781 1199117283837 1547928613605 899524679128 1495714480795 1196591493368 981733389269 1184663866396 937249971220 1217636880799 1567605094467 1392243948541 1496701724063 9117555121...
result:
ok 50000 numbers
Test #25:
score: -100
Wrong Answer
time: 50ms
memory: 56884kb
input:
10000 50000 1967 9497 461820510 9497 1178 319298273 1178 7445 145202113 7445 3034 902583404 3034 7501 928151869 7501 2487 459727120 2487 1927 411855531 1927 4807 105006725 4807 1992 299690675 1992 4558 246562304 4558 115 348147838 115 2218 732412173 2218 6098 36029103 6098 8912 215264673 8912 5974 7...
output:
1452728960259 1069309140104 1088859970692 1601829914205 1600074448672 918801493758 1556713604025 1468991923254 1032000884525 1120479986989 1584995341955 1225820113142 1115386685568 1125849996370 1624310125094 1042043642274 1642673371715 921569447932 1114209021067 1175110907921 1674220487453 13608173...
result:
wrong answer 13149th numbers differ - expected: '1480092951820', found: '1480072583672'