QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423775#5148. Tree Distancexlpg0713WA 557ms125920kbC++202.8kb2024-05-28 16:21:072024-05-28 16:21:07

Judging History

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

  • [2024-05-28 16:21:07]
  • 评测
  • 测评结果:WA
  • 用时:557ms
  • 内存:125920kb
  • [2024-05-28 16:21:07]
  • 提交

answer

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#define pb push_back
using ll = long long;
#define int long long
const int N = 4e5 + 10, M = 2e6 + 10;
std::vector<std::pair<int, int>> g[N], q[N];
int n, m, nn, rt, t, md, ms[N], sz[N], vs[N]; ll rs[N];
std::pair<int, ll> a[N]; int tp, st[N]; std::vector<int> vc[N];
namespace dis{
    ll D[N]; int d[N], c, f[20][N<<1], p[N];
    void pr(int x, int fa){
        d[x]=d[fa]+1,++c,p[x]=c,f[0][c]=x;
        for(auto [v,w]:g[x]) if(v!=fa){
            D[v] = D[x] + w;
            pr(v, x), f[0][++c] = x;
        }
    }
    void bd(){
        pr(1, 0); for(int i = 1; 1 << i <= c; i++)
                for(int j = 1; j <= c + 1 - (1 << i); j++)
        f[i][j]=d[f[i-1][j]]<d[f[i-1][j+(1<<i-1)]]?f[i-1][j]:f[i-1][j+(1<<i-1)];
    }
    int lca(int x, int y){
        if((x=p[x])>(y=p[y])) std::swap(x, y); int k=std::__lg(y-x+1);
        return d[f[k][x]]<d[f[k][y-(1<<k)+1]]?f[k][x]:f[k][y+1-(1<<k)];
    }
    ll ds(int x, int y){return D[x]+D[y]-2ll*D[lca(x,y)];}
} using dis::ds;
struct bt{
    ll t[N]; bt(){memset(t, 63, sizeof t);}
    void upd(int p,ll x){for(;p;p-=p&-p)t[p]=std::min(t[p],x);}
    ll qmi(int p){ll r=9e18;for(;p<=n;p+=p&-p)r=std::min(r,t[p]);return r;}
}T;
void fd(int x, int fa){
    sz[x] = 1, ms[x] = 0;
    for(auto [v,w]:g[x]) if(!vs[v]&&v!=fa){
        fd(v, x), sz[x] += sz[v];
        ms[x] = std::max(ms[x], sz[v]);
    } if((ms[x]=std::max(ms[x],nn-sz[x]))<md) md=ms[x],rt=x;
}
void gd(int x, int fa, ll d){
    a[++t] = {x, d};
    for(auto [v, w] : g[x]) 
        if(v != fa && !vs[v]) gd(v, x, d+w);
}
void sol(int x){
    vs[x] = 1; t = 0; gd(x, 0, 0);
    std::sort(a + 1, a + t + 1);
    tp = 0; for(int i = 1; i <= t; i++){
        while(tp&&a[st[tp]].second>a[i].second)tp--;
        if(tp) vc[a[i].first].pb(a[st[tp]].first); st[++tp] = i;
    } tp = 0; for(int i = t; i; i--){
        while(tp&&a[st[tp]].second>a[i].second)tp--;
        if(tp) vc[a[st[tp]].first].pb(a[i].first); st[++tp] = i;
    } for(auto [v,w]:g[x]) if(!vs[v])
        rt = 0, md = n, nn = sz[v], fd(v, x), sol(rt);
}
signed main(){
    // freopen("in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    std::cin >> n; for(int i = 1, u, v, w; i < n; i++)
        std::cin >> u >> v >> w, g[u].pb({v, w}), g[v].pb({u, w});
    std::cin >> m; for(int i = 1, l, r; i <= m; i++)
        std::cin >> l >> r, l >= r ? rs[i] = -1, void() : q[r].pb({l, i});
    dis::bd(); rt=0, md=n, nn=n; fd(1, 0), sol(rt);
    for(int i = 1; i <= n; i++){
        for(int j:vc[i]) T.upd(j, ds(i, j));
        for(auto [l,p]:q[i]) rs[p] = T.qmi(l);
    } for(int i = 1; i <= m; i++) std::cout << rs[i] << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16632kb

input:

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

output:

-1
3
7
7
2

result:

ok 5 number(s): "-1 3 7 7 2"

Test #2:

score: -100
Wrong Answer
time: 557ms
memory: 125920kb

input:

199999
31581 23211 322548833
176307 196803 690953895
34430 82902 340232856
36716 77480 466375266
7512 88480 197594480
95680 61864 679567992
19572 14126 599247796
188006 110716 817477802
160165 184035 722372640
23173 188594 490365246
54801 56250 304741654
10103 45884 643490340
127469 154479 214399361...

output:

1046265252
4557430888798830399
1131318
21418435
370008
4557430888798830399
15137404408
23405002
6822061629
4557430888798830399
8233810962
18725005
2103667
2103667
370008
8541785345
413562402
4557430888798830399
254661518
370008
255441910
6511855
9641696
8901321909
336966887
11346923
4557430888798830...

result:

wrong answer 1st numbers differ - expected: '29573323', found: '1046265252'