QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423771#5148. Tree Distancexlpg0713WA 392ms127752kbC++202.7kb2024-05-28 16:17:172024-05-28 16:17:19

Judging History

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

  • [2024-05-28 16:17:19]
  • 评测
  • 测评结果:WA
  • 用时:392ms
  • 内存:127752kb
  • [2024-05-28 16:17:17]
  • 提交

answer

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#define pb push_back
using ll = long long;
const int N = 5e5 + 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);
}
int 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';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 28796kb

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: 392ms
memory: 127752kb

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
471464
21418435
370008
4557430888798830399
15137404408
23405002
9809990276
4557430888798830399
8233810962
18725005
2103667
2103667
370008
8541785345
413562402
4557430888798830399
254661518
370008
154156124
6511855
21418435
24365422309
268925974
7410757
4557430888798830...

result:

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