QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692531#5439. Meet in the Middlel_rANdWA 3ms17376kbC++205.3kb2024-10-31 14:40:172024-10-31 14:40:23

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 14:40:23]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:17376kb
  • [2024-10-31 14:40:17]
  • 提交

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'