QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692303#5439. Meet in the MiddleDaniel777WA 5ms25896kbC++143.2kb2024-10-31 14:17:492024-10-31 14:17:49

Judging History

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

  • [2024-10-31 14:17:49]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:25896kb
  • [2024-10-31 14:17:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
typedef long long ll;
const int N = 1e5+5,M = 5e5+5;
vector< pii >tr1[N],tr2[N];
int n,m;
int A[M],B[M];
vector<int>q[N];
int dfn[N],rk[N<<1],dfcnt;
ll st[20][N<<1];
ll sum[N],ans[M];
ll cur[N];
int sz[N],rt,vis[N];
int cx,cy;
void dfs(int u,int fa)
{
    rk[dfn[u] = ++dfcnt] = u;
    for(auto [v,w]:tr2[u]) if(v != fa)
    {
        sum[v] = sum[u] + w;
        dfs(v,u);
        rk[++dfcnt] = u;
    }
}
ll Dist(int x,int y)
{
    int l = dfn[x],r = dfn[y];
    if(l > r) swap(l,r);
    int t = __lg(r-l+1);
    return sum[x] + sum[y] - 2*min(st[t][l],st[t][r-(1<<t)+1]);
}
void getrt(int u,int fa,int SZ)
{
    int mx = 0;
    sz[u] = 1;
    for(auto [v,w]:tr1[u]) if(v != fa && !vis[v])
    {
        getrt(v,u,SZ);
        sz[u] += sz[v];
        mx = max(mx,sz[v]);
    }
    mx = max(mx,SZ-sz[u]);
    if(mx*2 <= SZ) rt = u;
}
void qry(int u,int fa)
{
    for(auto id:q[u]) ans[id] = max(ans[id],max(Dist(cx,B[id])+cur[cx],Dist(cy,B[id])+cur[cy])+cur[u]);
    for(auto [v,w]:tr1[u]) if(v != fa && !vis[v]) qry(v,u);
}
void updt(int u,int fa)
{
    ll d1 = cur[cx] + cur[cy] + Dist(cx,cy);
    ll d2 = cur[cx] + cur[u] + Dist(cx,u);
    ll d3 = cur[cy] + cur[u] + Dist(cy,u);
    ll mx = max(d1,max(d2,d3));
    if(mx == d3) cx = u;
    else if(mx == d2) cy = u;
    for(auto [v,w]:tr1[u]) if(v != fa && !vis[v]) updt(v,u);
}
void init(int u,int fa)
{
    sz[u] = 1;
    for(auto [v,w]:tr1[u]) if(v != fa && !vis[v])
    {
        cur[v] = cur[u] + w;
        init(v,u);
        sz[u] += sz[v];
    }
}
void work(int u,int SZ)
{
    getrt(u,0,SZ);
    u = rt;
    vis[u] = 1;
    cur[u] = 0;
    init(u,0);
    cx = cy = u;
    for(auto [v,w]:tr1[u]) if(!vis[v])
    {
        qry(v,u);
        updt(v,u);
    }
    for(auto id:q[u])
    {
        ans[id] = max(ans[id],max(Dist(cx,B[id]) + cur[cx],Dist(cy,B[id]) + cur[cy]));
    }
    reverse(tr1[u].begin(),tr1[u].end());
    cx = cy = u;
    for(auto [v,w]:tr1[u]) if(!vis[v])
    {
        qry(v,u);
        updt(v,u);
    }
    reverse(tr1[u].begin(),tr1[u].end());
    for(auto [v,w]:tr1[u]) if(!vis[v]) work(v,sz[v]);
}
void solve()
{
    cin>>n;
    for(int i = 1;i <= n;i++) tr1[i].clear(),tr2[i].clear(),q[i].clear(),vis[i] = 0;
    for(int i = 1,u,v,w;i < n;i++)
    {
        cin>>u>>v>>w;
        tr1[u].pb(mkp(v,w));
        tr1[v].pb(mkp(u,w));
    }
    for(int i = 1,u,v,w;i < n;i++)
    {
        cin>>u>>v>>w;
        tr2[u].pb(mkp(v,w));
        tr2[v].pb(mkp(u,w));
    }
    sum[0] = dfcnt = 0;
    //O(1)求树上距离
    dfs(1,0);
    for(int i = 1;i <= 2*n-1;i++) st[0][i] = sum[rk[i]];
    for(int i = 1;i < 18;i++)
        for(int j = 1;j + (1<<i)<= 2*n;j++)
            st[i][j] = min(st[i-1][j],st[i-1][j+(1<<i-1)]);
    cin>>m;
    for(int i = 1;i <= m;i++)
    {
        cin>>A[i]>>B[i];
        ans[i] = 0;
        q[A[i]].push_back(i);
    }
    work(1,n);
    for(int i = 1;i <= m;i++) cout<<ans[i]<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    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: 5ms
memory: 25896kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

21

result:

wrong answer 1st numbers differ - expected: '6', found: '21'