QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#699869 | #5439. Meet in the Middle | Nityacke | WA | 0ms | 18012kb | C++20 | 3.8kb | 2024-11-02 11:01:59 | 2024-11-02 11:02:01 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1e5+5,M=5e5+5;
namespace IO{
inline char gc(){
static const int Rlen=1<<18|1;static char buf[Rlen],*p1,*p2;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>T get_integer(){
char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48;
while(isdigit(c=gc()))x=((x+(x<<2))<<1)+(c^48);return f?-x:x;
}
inline int gi(){return get_integer<int>();}
char obuf[(int)(2e7+7)],*oh=obuf;
inline void prt(char c){*oh++=c;}
inline void prt(const char *s){
while(*s)*oh++=*s++;
}
template<typename T>void prt(T a){
static char ch[23];int tl=0;
if(a<0)*oh++='-',a=-a;
do ch[++tl]=a%10;while(a/=10);
while(tl)*oh++=ch[tl--]^48;
}
template<typename T,class ...Args>
void prt(T a,Args...args){
prt(a),prt(args...);
}
struct obuf_flusher{
~obuf_flusher(){fwrite(obuf,1,oh-obuf,stdout);}
}Flusher;
}using namespace IO;
int T,n,q,ans[M];
vector<array<int,2>>Tr1[N],Tr2[N],Q[N];
namespace Tr{
int st[17][N],dfn[N],dn,dis[N];
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline void dfs(int x,int fa){
st[0][dfn[x]=++dn]=fa;
for(auto v:Tr2[x])
if(v[0]!=fa) dis[v[0]]=dis[x]+v[1],dfs(v[0],x);
}
inline void init(){
dn=0,dfs(1,0);
for(int j=1;j<17;++j)
for(int i=1;i+(1<<j)-1<=n;++i) st[j][i]=get(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
inline int lca(int u,int v){
if(u==v) return u;
if((u=dfn[u])>(v=dfn[v])) swap(u,v);
int L=__lg(v-(u++));
return get(st[L][u],st[L][v-(1<<L)+1]);
}
inline int dist(int u,int v){return dis[u]+dis[v]-2*dis[lca(u,v)];}
}using Tr::dist;
int st[N],rev[N],ed[N],dn,dep[N];
inline void pre(int x,int fa){
st[x]=++dn,rev[dn]=x;
for(auto v:Tr1[x])
if(v[0]!=fa) dep[v[0]]=dep[x]+v[1],pre(v[0],x);
ed[x]=dn;
}
inline int calc(int a,int b,int c,int d){return a==b?0:dist(a,b)+c+d;}
namespace ST{
#define node array<int,4>
node t[N<<2];
int tag[N<<2];
#define k1 (k<<1)
#define k2 (k<<1|1)
#define mid ((l+r)>>1)
array<int,2>pos[5];
inline node operator+(node A,node B){
node C=A;
pos[0]={A[0],A[2]},pos[1]={A[1],A[3]},pos[2]={B[0],B[2]},pos[3]={B[1],B[3]};
for(int i=0;i<=3;++i)
for(int j=i+1;j<=3;++j)
if(calc(pos[i][0],pos[j][0],pos[i][1],pos[j][1])>calc(C[0],C[1],C[2],C[3])) C={pos[i][0],pos[j][0],pos[i][1],pos[j][1]};
return C;
}
inline void up(int k){t[k]=t[k1]+t[k2];}
inline void build(int k=1,int l=1,int r=n){
tag[k]=0;
if(l==r) return t[k]={rev[l],rev[l],dep[rev[l]],dep[rev[l]]},void();
build(k1,l,mid),build(k2,mid+1,r),up(k);
}
inline void add(int k,int v){t[k][2]+=v,t[k][3]+=v,tag[k]+=v;}
inline void push(int k){if(tag[k]) add(k1,tag[k]),add(k2,tag[k]),tag[k]=0;}
inline void change(int L,int R,int val,int k=1,int l=1,int r=n){
if(L<=l&&R>=r) return add(k,val);
push(k);
if(L<=mid) change(L,R,val,k1,l,mid);
if(R>mid) change(L,R,val,k2,mid+1,r);
up(k);
}
}
inline void solve(int x,int fa){
node now=ST::t[1];
for(auto v:Q[x]) ans[v[1]]=max(calc(now[0],v[0],now[2],0),calc(now[1],v[0],now[3],0));
for(auto v:Tr1[x])
if(v[0]!=fa){
ST::change(1,n,v[1]),ST::change(st[v[0]],ed[v[0]],-2*v[1]);
solve(v[0],x);
ST::change(1,n,-v[1]),ST::change(st[v[0]],ed[v[0]],2*v[1]);
}
}
inline void solve(){
n=gi(),dn=0;
for(int i=1;i<=n;++i) Tr1[i].clear(),Tr2[i].clear(),Q[i].clear();
for(int i=1,u,v,w;i<n;++i) u=gi(),v=gi(),w=gi(),Tr1[u].pb({v,w}),Tr1[v].pb({u,w});
for(int i=1,u,v,w;i<n;++i) u=gi(),v=gi(),w=gi(),Tr2[u].pb({v,w}),Tr2[v].pb({u,w});
q=gi();
for(int i=1,u,v;i<=q;++i) u=gi(),v=gi(),Q[u].pb({v,i});
Tr::init(),pre(1,0),ST::build(),solve(1,0);
for(int i=1;i<=q;++i) prt(ans[i],'\n');
}
signed main(){
T=1;
while(T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 18012kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
12
result:
wrong answer 1st numbers differ - expected: '6', found: '12'