QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#334175 | #6111. Two Paths | FISHER_ | TL | 6835ms | 61352kb | C++14 | 5.9kb | 2024-02-21 12:30:40 | 2024-02-21 12:30:40 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5,Maxk=5e5;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int n,m,fa[Maxn+5]; ll dis[Maxn+5];
int dfn[Maxn+5],st[Maxn+5][20],cur;
vector<pair<int,int>> v[Maxn+5];
inline int Get(int x,int y) {return (dfn[x]<dfn[y])?x:y;}
inline int LCA(int x,int y)
{
if(x==y) return x; if((x=dfn[x])>(y=dfn[y])) swap(x,y);
int len=__lg(y-x++); return Get(st[x][len],st[y-(1<<len)+1][len]);
}
inline ll Dis(int x,int y) {return dis[x]+dis[y]-2*dis[LCA(x,y)];}
struct Node{int x,y;} f[Maxn+5],g[Maxn+5];
inline Node operator+(Node a,Node b)
{
if(a.x==0 && a.y==0) return b; if(b.x==0 && b.y==0) return a;
int ax=a.x,ay=a.y,bx=b.x,by=b.y;
ll s1=Dis(ax,ay),s2=Dis(bx,by),s3=Dis(ax,bx),s4=Dis(ay,by),s5=Dis(ax,by),s6=Dis(ay,bx);
ll mx=max(s1,max(s2,max(s3,max(s4,max(s5,s6)))));
if(mx==s1) return Node{ax,ay}; if(mx==s2) return Node{bx,by};
if(mx==s3) return Node{ax,bx}; if(mx==s4) return Node{ay,by};
if(mx==s5) return Node{ax,by}; if(mx==s6) return Node{ay,bx};
}
inline void dfs(int x,int f)
{
fa[x]=f,dfn[x]=++cur,st[cur][0]=f;
for(auto [y,z]:v[x]) if(y!=f) dis[y]=dis[x]+z,dfs(y,x);
}
inline void dfs1(int x,int fa)
{f[x]=Node{x,x}; for(auto [y,z]:v[x]) if(y!=fa) dfs1(y,x),f[x]=f[x]+f[y];}
inline void dfs2(int x,int fa)
{
static Node pr[Maxn+5],sf[Maxn+5];
Node res=g[x]+Node{x,x}; for(auto [y,z]:v[x]) if(y!=fa) pr[y]=res,res=res+f[y];
res=Node{0,0}; reverse(v[x].begin(),v[x].end());
for(auto [y,z]:v[x]) if(y!=fa) sf[y]=res,res=res+f[y];
reverse(v[x].begin(),v[x].end());
for(auto [y,z]:v[x]) if(y!=fa) g[y]=pr[y]+sf[y];
for(auto [y,z]:v[x]) if(y!=fa) dfs2(y,x);
}
inline int Check1() {For(i,1,n) if(v[i].size()>2) return 0; return 1;}
namespace T1
{
struct Point
{
ll x,y; inline Point() {}
inline Point(ll _x,ll _y): x(_x),y(_y) {}
}; vector<Point> t[Maxn*4+5];
inline bool operator<(Point a,Point b)
{return a.x<b.x || (a.x==b.x && a.y<b.y);}
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
int rt,rk[Maxn+5],id[Maxn+5],h[Maxn+5],tot; ll sum[Maxn+5];
int mn[Maxn+5][20];
inline void dfs(int x,int f,int k)
{
id[++tot]=x,rk[x]=tot,h[tot]=k;
for(auto [y,z]:v[x]) if(y!=f) dfs(y,x,z);
}
inline int Get(int l,int r)
{int len=__lg(r-l+1); return min(mn[l][len],mn[r-(1<<len)+1][len]);}
inline double Slope(Point a,Point b) {return 1.0*(b.y-a.y)/(b.x-a.x);}
inline auto Merge(vector<Point> v1,vector<Point> v2)
{
vector<Point> v3,v;
for(auto i:v1) v3.push_back(i);
for(auto i:v2) v3.push_back(i);
sort(v3.begin(),v3.end());
for(auto i:v3)
{
while(v.size()>1 && Slope(v[v.size()-2],v.back())<=
Slope(v.back(),i)) v.pop_back();
v.push_back(i);
} return v;
}
inline void Build(int l,int r,int p)
{
if(l==r) {t[p].push_back(Point(sum[l+1],sum[l])); return;}
int mid=(l+r)>>1; Build(l,mid,ls(p)),Build(mid+1,r,rs(p));
t[p]=Merge(t[ls(p)],t[rs(p)]);
}
inline ll Get(int p,int A,int B)
{
vector<Point> &v=t[p]; int sz=v.size(); double res=1.0*B/A;
int l=0,r=sz-1; while(l<r)
{
int mid=(l+r+1)/2;
if(Slope(v[mid-1],v[mid])>=res) l=mid;
else r=mid-1;
} auto [x,y]=v[l]; return 1ll*A*y-1ll*B*x;
}
inline ll Count(int nl,int nr,int l,int r,int p,int A,int B)
{
if(l<=nl && nr<=r) return Get(p,A,B);
int mid=(nl+nr)>>1; ll res=LLONG_MIN;
if(l<=mid) res=max(res,Count(nl,mid,l,r,ls(p),A,B));
if(r>mid) res=max(res,Count(mid+1,nr,l,r,rs(p),A,B));
return res;
}
inline void Run()
{
For(i,1,n) if(v[i].size()==1) {rt=i; break;}
dfs(rt,0,0); For(i,1,n) sum[i]=sum[i-1]+h[i];
For(i,1,n) mn[i][0]=h[i];
For(j,1,19) for(int i=1;i+(1<<j)-1<=n;++i)
mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
Build(1,n,1);
while(m--)
{
int x=rk[read()],y=rk[read()],A=read(),B=read();
if(x>y) swap(x,y),swap(A,B);
ll res=sum[x]*A+(sum[n]-sum[y])*B;
res=max(res,(sum[y]-sum[x+1])*B+sum[x]*A);
res=max(res,(sum[n]-sum[y])*B+(sum[y-1]-sum[x])*A);
ll now=Count(1,n,x,y-1,1,A,B);
now=now-sum[x]*A+sum[y]*B; res=max(res,now);
printf("%lld\n",res);
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
}
}
int main()
{
// freopen("C.in","r",stdin);
// freopen("C.out","w",stdout);
n=read(),m=read();
For(i,1,n-1)
{
int a=read(),b=read(),c=read();
v[a].emplace_back(b,c),v[b].emplace_back(a,c);
}
if(Check1()) {T1::Run(); return 0;}
dfs(1,0);
For(j,1,19) for(int i=1;i+(1<<j)-1<=n;++i)
st[i][j]=Get(st[i][j-1],st[i+(1<<j-1)][j-1]);
dfs1(1,0),dfs2(1,0);
while(m--)
{
int x=read(),y=read(),A=read(),B=read(),l=LCA(x,y);
ll ans=0;
for(int i=x;i!=l;i=fa[i])
{
Node a=f[i],b=g[i];
ll dx=max(Dis(x,a.x),Dis(x,a.y));
ll dy=max(Dis(y,b.x),Dis(y,b.y));
ans=max(ans,dx*A+dy*B);
}
for(int i=y;i!=l;i=fa[i])
{
Node a=f[i],b=g[i];
ll dx=max(Dis(x,b.x),Dis(x,b.y));
ll dy=max(Dis(y,a.x),Dis(y,a.y));
ans=max(ans,dx*A+dy*B);
}
printf("%lld\n",ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 38844kb
input:
6 4 1 2 4 2 5 5 2 3 7 3 6 5 3 4 4 1 4 1 1 1 4 2 1 5 6 1 1 5 6 1 10
output:
18 32 18 160
result:
ok 4 number(s): "18 32 18 160"
Test #2:
score: 0
Accepted
time: 4ms
memory: 31292kb
input:
2 1 1 2 1 1 2 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 3ms
memory: 30216kb
input:
2 10 1 2 2 1 2 1 1 1 2 1 2 1 2 1 3 1 2 2 1 1 2 2 2 1 2 3 1 1 2 3 2 1 2 3 3 1 2 2 3 1 2 1 3
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 77ms
memory: 30856kb
input:
10 500000 4 5 576 5 8 218 1 10 678 1 9 2540 7 8 2023 2 7 5510 2 9 8454 4 6 22 3 9 5248 2 5 35782 82142 1 2 95412 85188 4 5 82466 22193 3 6 22169 67901 4 10 67229 30987 1 10 68282 17858 1 8 53726 3246 5 8 13913 74110 2 8 30052 7204 1 4 95255 48216 2 5 41392 98997 3 8 8435 5947 1 5 22067 21610 7 9 343...
output:
674365186 1454303268 477920681 1359445921 1501996827 1320778726 889342640 1582045824 426346196 1792561801 789005461 166905972 478560756 71705653 343648830 901237204 420263788 1710700661 309792440 335240094 1852278021 1679904905 1055408048 1644275016 563316675 602184744 873340490 815015664 1356022267...
result:
ok 500000 numbers
Test #5:
score: 0
Accepted
time: 189ms
memory: 27328kb
input:
100 500000 4 63 6394 57 91 2108 5 52 9292 6 63 3151 52 62 1006 13 19 8138 42 59 6102 3 95 275 36 80 8426 20 84 7879 32 100 4423 71 89 9590 55 98 240 46 100 7470 70 92 7417 43 54 6092 24 41 230 93 94 6591 8 92 2558 34 63 7534 4 36 5620 17 93 987 35 96 1288 42 68 6280 72 89 9818 43 57 8266 26 62 2431 ...
output:
30730511688 35868047826 94569561805 103860674856 108734641138 103921529851 151172279864 108994447520 79859941598 90637244010 113651189677 26614889256 54138181416 163935808262 43257729984 101945300646 27547811269 67543514171 84292164869 59484837480 117300068794 77146438694 27400485192 55424042658 628...
result:
ok 500000 numbers
Test #6:
score: 0
Accepted
time: 6180ms
memory: 60544kb
input:
200000 500000 83239 106513 1257 142726 196994 1263 95614 142588 7488 88575 193932 8123 31396 180633 1564 37559 131657 927 143893 157390 740 117889 182920 7831 103309 142289 6864 15478 36228 2717 5896 6815 5902 42275 184396 2646 21903 63571 8966 23873 42450 2721 36540 46154 9467 155293 161123 8588 54...
output:
5966882576104305 7271792958583645 8570461339781342 9614114352538144 6712681170527500 9409581586879995 6304678086998919 6559831613756394 4016495625693024 4381351843519688 4971908463803118 8759545709797016 11418325924391126 8912046248703475 10780907424911508 3112723787504739 9395431732704804 851233289...
result:
ok 500000 numbers
Test #7:
score: 0
Accepted
time: 71ms
memory: 38832kb
input:
10 500000 7 8 6474 3 4 6652 4 5 5193 6 9 457 5 9 3937 1 7 7261 2 5 6472 6 8 6967 3 10 8997 2 9 77462 28703 3 7 31026 16732 2 6 39340 36431 6 9 95641 333 4 8 17377 97247 2 4 20769 98147 4 6 425 42124 4 8 53119 54974 2 4 49307 3731 1 7 13417 95608 7 8 36330 40656 6 10 16594 36336 1 6 47819 1121 1 3 93...
output:
2723123845 841480408 1828727322 1988211389 2006138424 2972774483 878701873 1811610573 1614909795 3697830616 1573037298 1336010492 685083521 3657916506 2557058802 3370810317 3011684921 862077669 2124928512 3326043566 1360831395 1603107540 3131147303 1037179764 1973141216 1587191713 747094784 36277104...
result:
ok 500000 numbers
Test #8:
score: 0
Accepted
time: 178ms
memory: 38536kb
input:
100 500000 40 72 2893 46 57 7594 13 90 4014 32 59 8870 4 81 4432 59 94 8856 59 96 4895 96 100 9950 32 80 8362 5 89 1777 36 69 2134 24 62 9978 21 65 3506 49 61 6056 33 48 5740 1 30 4143 30 60 8914 60 70 4900 66 93 6395 10 68 1687 10 95 2472 4 20 3135 2 17 9637 56 78 4429 20 27 2053 52 89 6906 27 39 9...
output:
106913710770 4495733708 102758976134 80160799892 76732267750 47039029473 72520507589 73042063332 73155659164 70949908024 18019999665 55814535350 72254712051 121025392740 66270956091 135577152247 39206666175 97754289402 83622700164 89895046420 147890155522 62926235281 108657350392 100238158900 814086...
result:
ok 500000 numbers
Test #9:
score: 0
Accepted
time: 6224ms
memory: 60112kb
input:
200000 500000 72622 96340 7225 16757 66347 2999 101297 187932 6437 49037 154632 460 124025 196592 9940 153072 170123 1421 34394 199313 4817 32364 32518 5106 88700 199062 8686 31819 36499 9765 52871 159318 6576 1498 113000 6088 87532 137708 9913 18424 42545 9372 10501 33545 5958 23767 170025 2704 187...
output:
14850031235173232 6999821359673356 13994322220418811 15658897860429808 5566180270698198 7768919631255131 7795054483438192 7419776394069074 12641505965465227 7472188388977804 15268455327661860 10901394489199617 8199280990426768 12441824458056512 5059765147523162 8301785128173369 6921399963160754 9272...
result:
ok 500000 numbers
Test #10:
score: 0
Accepted
time: 75ms
memory: 38588kb
input:
10 500000 7 8 6564 4 8 6189 3 9 5516 2 4 8374 2 9 4364 7 10 7523 6 8 9898 5 8 7016 1 5 2345 5 8 51845 42560 4 5 55887 98340 3 8 49610 54530 9 10 22945 35062 3 8 3458 95253 3 6 23153 11481 1 8 34851 37986 5 9 87362 27198 1 7 55997 43106 1 7 75611 27271 7 8 71599 78148 6 7 34117 75458 2 4 79390 55048 ...
output:
1161870605 3095430318 1673745050 1133235480 1802853531 892085090 1010217393 2190048410 2217209026 2761113977 2448810841 2339726206 1900526448 2923869030 1282299167 2882083522 2590862660 2125646342 2738520864 1608180381 1666730547 2125172192 2345809770 1603963890 3685256440 2391830675 183542487 93557...
result:
ok 500000 numbers
Test #11:
score: 0
Accepted
time: 150ms
memory: 38668kb
input:
100 500000 64 80 6288 35 50 3079 47 52 1840 5 69 4588 3 14 5154 76 80 5382 35 60 9496 19 61 9625 71 73 9786 7 46 9867 5 15 9846 14 57 7663 39 52 9476 21 38 3153 44 63 1358 60 67 4899 56 59 302 8 52 104 50 56 2937 28 72 8543 85 91 7835 16 87 5283 29 77 3795 11 84 6769 49 65 1585 45 51 1354 2 89 9853 ...
output:
72202925787 97514852513 56756195638 37288713475 35676803180 90017144414 38927158215 28601206274 14400684154 45932515989 77207561276 59432631660 70376380240 78182150824 76907451131 97790656742 61036431338 66756945882 44962902462 95491099215 84137846038 57887416052 58421189377 45768814245 47300757994 ...
result:
ok 500000 numbers
Test #12:
score: 0
Accepted
time: 6835ms
memory: 61352kb
input:
200000 500000 84618 98845 7176 107087 196559 4404 173709 192096 4717 122383 132949 1263 13177 34882 5439 139807 160157 1421 45167 91345 9766 107962 187717 2148 66125 151170 6686 63358 86085 5420 92294 134701 5058 113293 149067 2818 52824 164065 9708 44586 64319 6527 52176 147205 1116 36120 153708 18...
output:
10077660798661166 6673502274389958 12939177208895010 9047200007665110 6573554974664500 5242597508990838 13676616292679150 9704815634833183 11561184450694770 12472403863791083 13122447381660824 13320490331795583 8658969745868196 8796014087160251 13063721599988841 12566284718749275 7973072528332602 11...
result:
ok 500000 numbers
Test #13:
score: 0
Accepted
time: 72ms
memory: 38912kb
input:
10 500000 5 10 9359 6 8 2622 3 4 32 1 5 6291 2 5 4790 6 7 9273 5 7 7916 2 3 1256 7 9 6094 1 4 93524 56417 1 4 72235 21165 1 8 59881 96821 3 7 60649 69792 3 7 40702 86345 2 7 89678 55741 3 7 83505 90656 9 10 91223 25352 6 10 12287 11104 5 8 94433 78823 4 6 19397 21614 2 6 56138 89726 3 7 87392 7152 2...
output:
2513828544 1912738490 2824268570 1764473685 1654088085 1931893217 2364747645 2037769347 362591929 2301745394 631573827 2454351592 1431346800 1917618468 112297763 185018940 1653764936 1250254372 1568465383 1292309244 236168002 506864435 425491147 2028002330 476710384 1808277470 2247989250 1318111291 ...
result:
ok 500000 numbers
Test #14:
score: 0
Accepted
time: 185ms
memory: 38584kb
input:
100 500000 8 10 4275 5 60 2756 55 71 6562 46 53 306 40 85 8980 24 97 1909 59 90 8289 58 77 9299 38 74 9722 5 95 9173 34 42 7558 35 92 8051 78 86 5446 29 63 4443 72 78 3872 26 100 246 35 50 203 73 74 2605 53 74 6774 66 81 6888 39 66 4686 31 62 4727 3 92 9440 71 88 4918 18 90 9628 22 46 9995 28 49 991...
output:
65913039086 86901503285 145182328228 51391603893 107334514650 33026739520 141561395797 94885846572 85557851805 95450858526 43327973728 76933550118 105576354578 116690159952 127214406241 57156892577 92243211803 2929303556 60914681674 87520089774 88616664175 89811058923 60767857476 39044073040 6597593...
result:
ok 500000 numbers
Test #15:
score: -100
Time Limit Exceeded
input:
200000 500000 48263 193405 8782 39826 138335 6086 43411 47049 42 32460 100163 6561 110839 195838 6052 5325 169299 7212 2594 89322 851 46973 138509 8277 45626 176835 6893 94589 172557 9834 46014 69648 1541 10815 31117 7070 123771 141531 2871 72939 179823 4185 68124 69369 7576 127353 144997 9295 96779...
output:
4813047735928155 13563121456000208 10623977740697384 12368325537868986 9906634169705396 15509065513494903 5103499979323596 12246478270010336 14933318539416384 8682385540396731 6020406730020679 14413092183185878 12398399473755534 14259938583507292 11726545588336542 12617036028393990 11053303327631314...