QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692531 | #5439. Meet in the Middle | l_rANd | WA | 3ms | 17376kb | C++20 | 5.3kb | 2024-10-31 14:40:17 | 2024-10-31 14:40:23 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
int read(){
int ret=0,f=1;char c=getchar();
while(c>57||c<48){if(c=='-')f= -1;c=getchar();}
while(c<=57&&c>=48)ret=(ret<<3)+(ret<<1)+(c-48),c=getchar();
return ret*f;
}
void write(int x){
if(x<0) x= -x,putchar('-');
if(x>9)write(x/10);
putchar(x%10+48);
}
const int maxn=1e5+5;
const int mod =1e9+7;
int n,m;
namespace T1{
vector<pair<int,int> >G[maxn];
void link(int x,int y,int z){
G[x].push_back({y,z});
G[y].push_back({x,z});
}
int dis[maxn],dfn[maxn],st[18][maxn],dcnt,dep[maxn];
int mind(int x,int y){return dep[x]<dep[y]?x:y;}
void dfs_lca(int u,int f){
dfn[u]=++dcnt,dep[u]=dep[f]+1;
st[0][dfn[u]]=f;
for(auto[v,w]:G[u]){
if(v==f)continue;
dis[v]=dis[u]+w;
dfs_lca(v,u);
}
}
void init_lca(){
dfs_lca(1,0);
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[i][j]=mind(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
}
}
int lca(int x,int y){
if(x==y)return x;
x=dfn[x],y=dfn[y];
if(x>y)swap(x,y);
int s=__lg(y-x++);
return mind(st[s][x],st[s][y-(1<<s)+1]);
}
inline int dist(int x,int y){return dis[x]+dis[y]-dis[lca(x,y)]*2;}
void clear(){
for(int i=1;i<=n;i++)G[i].clear();dcnt=0;
}
}
namespace T2{
vector<pair<int,int> >G[maxn];
void link(int x,int y,int z){
G[x].push_back({y,z});
G[y].push_back({x,z});
}
int dis[maxn],dfn[maxn],st[18][maxn],dcnt,dep[maxn];
int mind(int x,int y){return dep[x]<dep[y]?x:y;}
void dfs_lca(int u,int f){
dfn[u]=++dcnt;dep[u]=dep[f]+1;
st[0][dfn[u]]=f;
for(auto[v,w]:G[u]){
if(v==f)continue;
dis[v]=dis[u]+w;
dfs_lca(v,u);
}
}
void init_lca(){
dfs_lca(1,0);
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[i][j]=mind(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
}
}
int lca(int x,int y){
if(x==y)return x;
x=dfn[x],y=dfn[y];
if(x>y)swap(x,y);
int s=__lg(y-x++);
return mind(st[s][x],st[s][y-(1<<s)+1]);
}
int root=1;
inline int dist(int x,int y){
return dis[x]+dis[y]+dis[root]*2-dis[lca(x,root)]*2-dis[lca(y,root)]*2+T1::dist(x,y);
}
struct node{
int u,v,dis;
node(){u=0,v=0,dis=-1;}
node(int x){u=x,v=x,dis=dist(x,x);}
node(int x,int y){u=x,v=y,dis=dist(x,y);}
}dp[maxn][2];
bool operator<(node x,node y){return x.dis<y.dis;}
node operator+(node x,node y){
if(x.dis==-1||y.dis==-1)return max(x,y);
return max({node(x.u,x.v),node(y.u,y.v),node(x.u,y.u),node(x.u,y.v),node(x.v,y.u),node(x.v,y.v)});
}
void dfs1(int u,int f){
dp[u][0]=node(u);
for(auto [v,w]:G[u]){
if(v==f)continue;
dfs1(v,u);
root=u;
dp[u][0]=dp[u][0]+dp[v][0];
}
// cerr<<u<<' '<<dp[u][0].u<<' '<<dp[u][0].v<<endl;
}
node pre[maxn];int pcnt=0;
void dfs2(int u,int f){
root=u;
pcnt=0;
for(int i=0;i<G[u].size();i++){
auto[v,w]=G[u][i];
if(v==f)continue;
pcnt++;
pre[pcnt]=pre[pcnt-1]+dp[v][0];
}
node suf;int scnt=0;
for(int i=(int){G[u].size()}-1;i>=0;i--){
auto[v,w]=G[u][i];
if(v==f)continue;
root=v;
scnt++;
dp[v][1]=suf+pre[pcnt-scnt]+dp[u][1]+node(u);
root=u;
suf=dp[v][0]+suf;
}
for(auto [v,w]:G[u]){
if(v==f)continue;
dfs2(v,u);
}
}
int query(int x,int y){
root=y;
// int ax=1,ay=1;
// for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
// if(dist(ax,ay)<dist(i,j))ax=i,ay=j;
// }
// int ud=dis[y]+dis[ax]-dis[lca(y,ax)]*2+T1::dist(x,ax);
// int vd=dis[y]+dis[ay]-dis[lca(y,ay)]*2+T1::dist(x,ay);
// cerr<<ax<<' '<<ay<<endl;
// cerr<<dp[y][0].u<<' '<<dp[y][0].v<<endl;
// cerr<<dp[y][1].u<<' '<<dp[y][1].v<<endl;
node pah=dp[y][0]+dp[y][1];
int ud=dis[y]+dis[pah.u]-dis[lca(y,pah.u)]*2+T1::dist(x,pah.u);
int vd=dis[y]+dis[pah.v]-dis[lca(y,pah.v)]*2+T1::dist(x,pah.v);
return max(ud,vd);
}
void clear(){
for(int i=1;i<=n;i++)G[i].clear(),dp[i][0]=dp[i][1]=node();dcnt=0;
}
}
void solve(){
T1::clear(),T2::clear();
n=read();
for(int i=1;i<n;i++){
int x=read(),y=read(),z=read();
T1::link(x,y,z);
}
for(int i=1;i<n;i++){
int x=read(),y=read(),z=read();
T2::link(x,y,z);
}
T1::init_lca();
T2::init_lca();
T2::dfs1(1,0);
T2::dfs2(1,0);
m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
write(T2::query(x,y)),putchar('\n');
}
}
signed main(){
// freopen("move.in","r",stdin);
// freopen("move.out","w",stdout);
int T=1;
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 17376kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
5
result:
wrong answer 1st numbers differ - expected: '6', found: '5'