QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334177 | #6111. Two Paths | FISHER_ | WA | 556ms | 61456kb | C++14 | 6.3kb | 2024-02-21 12:33:31 | 2024-02-21 12:33:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
int len=0;
char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
#if ONLINE_JUDGE
#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline int read(){
reg char ch=gh();
reg int x=0;
reg char t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
return t?-x:x;
}
inline void putc(char ch){
out[len++]=ch;
}
template<class T>
inline void write(T x){
if(x<0)putc('-'),x=-x;
if(x>9)write(x/10);
out[len++]=x%10+48;
}
inline void flush(){
fwrite(out,1,len,stdout);
len=0;
}
inline char getc(){
char ch=gh();
while(ch<'A'||ch>'Z') ch=gh();
return ch;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=2e5+10,Q=5e5+10;
int n,q,X,Y,head[N],fa[N],cnt;
ll dep[N],ans[Q],mx[N];
bool vis[N];
struct Edge{
int to,nxt,w;
}a[N<<1];
inline void add(int u,int v,int w){
a[++cnt]={v,head[u],w};
head[u]=cnt;
}
struct Query{
int u,v,a,b;
}qr[Q];
inline void dfs0(int x,int fa){
for(int i=head[x];i;i=a[i].nxt){
int t=a[i].to;
if(t==fa) continue;
dep[t]=dep[x]+a[i].w;
dfs0(t,x);
}
}
namespace ST{
int dfn[N],lg[N],tim,st[19][N];
vector<pii>son[N];
inline void dfs(int x,int f){
st[0][dfn[x]=++tim]=f;
mx[x]=dep[x];
for(int i=head[x];i;i=a[i].nxt){
int t=a[i].to;
if(t==f) continue;
dep[t]=dep[x]+a[i].w,fa[t]=x;
dfs(t,x);
mx[x]=max(mx[x],mx[t]);
son[x].push_back(mpr(dfn[t],t));
}
}
inline int cmp(int x,int y){
return dep[x]<dep[y]?x:y;
}
inline int LCA(int x,int y){
if(x==y) return x;
x=dfn[x],y=dfn[y];
if(x>y) swap(x,y);
x++;
int i=lg[y-x+1],p=1<<i;
return cmp(st[i][x],st[i][y-p+1]);
}
inline ll dis(int u,int v){
return dep[u]+dep[v]-dep[LCA(u,v)]*2;
}
inline int find(int x,int y){
return (*(--upper_bound(son[x].begin(),son[x].end(),mpr(dfn[y],N)))).sec;
}
struct Line{
int a,b;
Line(int x=0,int y=0){ a=x,b=y; }
inline friend bool operator<(const Line &a,const Line &b){
return dis(a.a,a.b)<dis(b.a,b.b);
}
inline friend Line operator+(const Line &a,const Line &b){
return max({a,b,Line(a.a,b.a),Line(a.a,b.b),Line(a.b,b.a),Line(a.b,b.b)});
}
}s[N];
inline void dfs2(int x,int f){
s[x]=Line(x,x);
for(int i=head[x];i;i=a[i].nxt){
int t=a[i].to;
if(t==f) continue;
dfs2(t,x);
s[x]=s[x]+s[t];
}
}
inline void init(int x){
dep[x]=fa[x]=tim=0;
for(int i=1;i<=n;i++)
son[i].clear();
dfs(x,0);
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<i-1)]);
for(int i=2;i<=n;i++)
lg[i]=lg[i>>1]+1;
dfs2(x,0);
}
}
using ST::find;
using ST::init;
using ST::Line;
using ST::LCA;
using ST::dis;
int id[N];
ll pr[N],sf[N],prs[N],sfs[N],pmx[N];
inline void dfs(int x,int fa){
for(int i=head[x];i;i=a[i].nxt){
int t=a[i].to;
if(t==fa) continue;
id[t]=id[x];
dfs(t,x);
}
}
int main(){
// freopen("path1.in","r",stdin);
// freopen("path1.ans","w",stdout);
srand(time(0));
n=read(),q=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
for(int i=1;i<=q;i++){
int u=read(),v=read(),A=read(),B=read();
qr[i]={u,v,A,B};
}
dfs0(1,0);
ll mxd=0;
for(int i=1;i<=n;i++)
if(dep[i]>mxd) mxd=dep[i],X=i;
dep[X]=mxd=0;
dfs0(X,0);
for(int i=1;i<=n;i++)
if(dep[i]>mxd) mxd=dep[i],Y=i;
init(X);
for(int i=1;i<=q;i++){
int u=qr[i].u,v=qr[i].v,a=qr[i].a,b=qr[i].b;
int l=LCA(u,v);
if(l!=v){
Line tmp=ST::s[find(l,v)];
ans[i]=max(ans[i],a*dep[u]+b*max(dis(v,tmp.a),dis(v,tmp.b)));
}
if(l!=u){
Line tmp=ST::s[find(l,u)];
ans[i]=max(ans[i],b*dep[v]+a*max(dis(u,tmp.a),dis(u,tmp.b)));
}
}
init(Y);
for(int i=1;i<=q;i++){
int u=qr[i].u,v=qr[i].v,a=qr[i].a,b=qr[i].b;
int l=LCA(u,v);
if(l!=v){
Line tmp=ST::s[find(l,v)];
ans[i]=max(ans[i],a*dep[u]+b*max(dis(v,tmp.a),dis(v,tmp.b)));
}
if(l!=u){
Line tmp=ST::s[find(l,u)];
ans[i]=max(ans[i],b*dep[v]+a*max(dis(u,tmp.a),dis(u,tmp.b)));
}
}
vector<int>vec;
vec.push_back(0);
for(int i=X;i;i=fa[i])
vec.push_back(i),vis[i]=1,id[i]=vec.size()-1;
if(vec.size()<n){
for(int i=1;i<vec.size();i++){
ll v=0;
for(int j=head[vec[i]];j;j=a[j].nxt){
int t=a[j].to;
if(vis[t]) continue;
v=max(v,mx[t]-dep[vec[i]]);
id[t]=i,dfs(t,vec[i]);
}
pr[i]=dep[X]-dep[vec[i]]+v,sf[i]=dep[vec[i]]+v;
prs[i]=dep[X]-dep[vec[i]],sfs[i]=dep[vec[i]];
}
for(int i=1;i<=q;i++){
int u=qr[i].u,v=qr[i].v,a=qr[i].a,b=qr[i].b;
if(id[u]>id[v]) swap(u,v),swap(a,b);
int l=id[u]+1,r=id[v]-1;
if(l<r){
ll mx=0;
pmx[l-1]=0;
for(int j=l;j<=r;j++)
pmx[j]=max(pmx[j-1],pr[j]);
for(int k=l+1;k<=r;k++)
mx=max(mx,a*pmx[k-1]+b*sf[k]);
ans[i]=max(ans[i],mx+a*(dep[u]-dep[X])+b*(dep[v]-dep[vec[r+1]]*2));
}
}
}
for(int i=1;i<=q;i++)
write(ans[i]),putc('\n');
flush();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9988kb
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: 0ms
memory: 10212kb
input:
2 1 1 2 1 1 2 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 10184kb
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: 58ms
memory: 28916kb
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: 96ms
memory: 29796kb
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: 556ms
memory: 61456kb
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: -100
Wrong Answer
time: 69ms
memory: 29044kb
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 850332000 2124928512 3326043566 1360831395 1603107540 3131147303 1037179764 1973141216 1587191713 747094784 36277104...
result:
wrong answer 18th numbers differ - expected: '862077669', found: '850332000'