QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#309223#5439. Meet in the MiddleRong7TL 0ms0kbC++147.3kb2024-01-20 15:47:152024-01-20 15:47:16

Judging History

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

  • [2024-01-20 15:47:16]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-01-20 15:47:15]
  • 提交

answer

// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

#define int long long

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
    int llen;
    inline int get_string (char c[], int &len = llen){
        len = 0;
        read_char = getchar ();
        while (read_char == ' ' || read_char == '\n' || read_char == '\r')
            read_char = getchar ();
        while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
            c[++ len] = read_char;
            read_char = getchar ();
        }
        return len;
    }
}

#define log2_(x) (31 ^ __builtin_clz (x))

const int N = 2e5 + 5, LOG = 17;
int T, n, Q;
int idx, dfn[N << 1], rep[N << 1], dep[N << 1], st[LOG + 5][N << 1];
int d2[N], d1[N];
int firs[N], nex[N << 1], to[N << 1], w[N << 1], tot;
vector < pair < int , int > > gto[N];
inline void Add (int u, int v, int l){ // for Tree 1
    ++ tot;
    nex[tot] = firs[u];
    firs[u] = tot;
    to[tot] = v;
    w[tot] = l;
}
inline void Connect (int u, int v, int l){ // for Tree 1
    gto[u].push_back (make_pair (v, l));
}

inline int get_mindep (int u, int v){ // for Tree 2
    return dep[u] < dep[v] ? u : v;
}
inline int LCA_t2 (int u, int v){ // for Tree 2
    u = dfn[u], v = dfn[v];
    if (u > v)
        swap (u, v);
    int p = log2_ (v - u + 1);
    return get_mindep (st[p][u], st[p][v - (1 << p) + 1]);
}
inline int dis2 (int u, int v){ // for Tree 2
    int lca = LCA_t2 (u, v);
    return d2[u] + d2[v] - (d2[lca] << 1);
}
inline void init1 (int u, int father){ // for Tree 2
    dep[u] = dep[father] + 1;
    rep[dfn[u] = ++ idx] = u;
    st[0][dfn[u]] = u;
    for (int e = firs[u], v;e;e = nex[e]){
        v = to[e];
        if (v == father)
            continue;
        d2[v] = d2[u] + w[e];
        init1 (v, u);
        rep[++ idx] = u;
        st[0][idx] = u;
    }
}

int ord[N], dfs[N], id, sz[N];
int ans[N << 2];
vector < pair < int , int > > Que[N];

void init2 (int u, int father){ // for Tree 1
    ord[u] = ++ id;
    dfs[id] = u;
    sz[u] = 1;
    for (auto e : gto[u]){
        int v = e.first;
        if (v == father)
            continue;
        d1[v] = d1[u] + e.second;
        init2 (v, u);
        sz[u] += sz[v];
    }
}

namespace Sgt {
    #define lson(p) ((p) << 1)
    #define rson(p) ((p) << 1 | 1)
    struct sgtree {
        int l, r;
        int a[2], b[2], tag;
        sgtree (int _l = 0, int _r = 0){
            l = _l;
            r = _r;
            a[0] = a[1] = b[0] = b[1] = tag = 0;
        }
    } tr[N << 2];
    inline void put_tag (int p, int x){
        tr[p].tag += x;
        tr[p].b[0] += x;
        tr[p].b[1] += x;
    }
    inline void push_up (int p){
        int res = 0;
        if (dis2 (tr[lson (p)].a[0], tr[lson (p)].a[1]) + tr[lson (p)].b[0] + tr[lson (p)].b[1] > res){
            res = dis2 (tr[lson (p)].a[0], tr[lson (p)].a[1]) + tr[lson (p)].b[0] + tr[lson (p)].b[1];
            tr[p].a[0] = tr[lson (p)].a[0];
            tr[p].a[1] = tr[lson (p)].a[1];
            tr[p].b[0] = tr[lson (p)].b[0];
            tr[p].b[1] = tr[lson (p)].b[1];
        }
        if (dis2 (tr[rson (p)].a[0], tr[rson (p)].a[1]) + tr[rson (p)].b[0] + tr[rson (p)].b[1] > res){
            res = dis2 (tr[rson (p)].a[0], tr[rson (p)].a[1]) + tr[rson (p)].b[0] + tr[rson (p)].b[1];
            tr[p].a[0] = tr[rson (p)].a[0];
            tr[p].a[1] = tr[rson (p)].a[1];
            tr[p].b[0] = tr[rson (p)].b[0];
            tr[p].b[1] = tr[rson (p)].b[1];
        }
        for (int i = 0;i < 2;++ i)
            for (int j = 0;j < 2;++ j)
                if (dis2 (tr[lson (p)].a[i], tr[rson (p)].a[j]) + tr[lson (p)].b[i] + tr[rson (p)].b[j] > res){
                    res = dis2 (tr[lson (p)].a[i], tr[rson (p)].a[j]) + tr[lson (p)].b[i] + tr[rson (p)].b[j];
                    tr[p].a[0] = tr[lson (p)].a[i];
                    tr[p].b[0] = tr[lson (p)].b[i];
                    tr[p].a[1] = tr[rson (p)].a[j];
                    tr[p].b[1] = tr[rson (p)].b[j];
                }
    }
    inline void push_down (int p){
        if (tr[p].tag){
            put_tag (lson (p), tr[p].tag);
            put_tag (rson (p), tr[p].tag);
            tr[p].tag = 0;
        }
    }
    inline void Build (int p, int l, int r){
        tr[p].l = l;
        tr[p].r = r;
        if (l == r){
            tr[p].a[0] = tr[p].a[1] = dfs[l];
            tr[p].b[0] = tr[p].b[1] = d1[dfs[l]];
            tr[p].tag = 0;
            return ;
        }
        int mid = (l + r) >> 1;
        Build (lson (p), l, mid);
        Build (rson (p), mid + 1, r);
        push_up (p);
    }
    inline void Update (int p, int l, int r, int x){
        if (l > r)
            return ;
        if (l <= tr[p].l && tr[p].r <= r){
            put_tag (p, x);
            return ;
        }
        push_down (p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if (l <= mid)
            Update (lson (p), l, r, x);
        if (r > mid)
            Update (rson (p), l, r, x);
        push_up (p);
    }
} using namespace Sgt;

void Solve (int u, int father){
    for (auto x : Que[u])
        ans[x.second] = max (dis2 (tr[1].a[0], x.first) + tr[1].b[0], dis2 (tr[1].a[1], x.first) + tr[1].b[1]);
    for (auto e : gto[u]){
        int v = e.first, we = e.second;
        if (v == father)
            continue;
        Update (1, 1, ord[v] - 1, we);
        Update (1, ord[v] + sz[v], n, we);
        Update (1, ord[v], ord[v] + sz[v] - 1, - we);
        Solve (v, u);
        Update (1, 1, ord[v] - 1, - we);
        Update (1, ord[v] + sz[v], n, - we);
        Update (1, ord[v], ord[v] + sz[v] - 1, we);
    }
}

signed main (){
    io::read (T);
    io::read (n), io::read (Q);
    for (int i = 1, u, v, l;i < n;++ i){
        io::read (u), io::read (v), io::read (l);
        Connect (u, v, l);
        Connect (v, u, l);
    }
    for (int i = 1, u, v, l;i < n;++ i){
        io::read (u), io::read (v), io::read (l);
        Add (u, v, l);
        Add (v, u, l);
    }
    init1 (1, 0);
    for (int i = 1;i <= LOG;++ i)
        for (int j = 1;j <= idx;++ j){
            st[i][j] = st[i - 1][j];
            if (j + (1 << (i - 1)) <= idx)
                st[i][j] = get_mindep (st[i][j], st[i - 1][j + (1 << (i - 1))]);
        }
    init2 (1, 0);
    Build (1, 1, n);
    for (int i = 1, u, v;i <= Q;++ i){
        io::read (u), io::read (v);
        Que[u].push_back (make_pair (v, i));
    }
    Solve (1, 0);
    for (int i = 1;i <= Q;++ i)
        io::write (ans[i]), puts ("");
    return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

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

output:


result: