QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94570#5249. Banditsmaomao90#TL 0ms0kbC++175.5kb2023-04-06 17:56:282023-04-06 17:56:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-06 17:56:31]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-04-06 17:56:28]
  • 提交

answer


// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 100005;
const int MAXL = 20;

#define assert(x) while (!(x)) cout << "HI"

int n, q;
iii eg[MAXN];
vii adj[MAXN];

int sub[MAXN], cl[MAXN], cp[MAXN];
ll d[MAXL][MAXN];
int getsub(int u, int p, int l) {
    sub[u] = 1;
    for (auto [v, c] : adj[u]) {
        if (v == p || cl[v]) {
            continue;
        }
        d[l - 1][v] = d[l - 1][u] + c;
        sub[u] += getsub(v, u, l);
    }
    return sub[u];
}
int getcent(int u, int p, int s) {
    for (auto [v, c] : adj[u]) {
        if (v == p || cl[v]) {
            continue;
        }
        if (sub[v] > s / 2) {
            return getcent(v, u, s);
        }
    }
    return u;
}
void build(int u, int p, int l) {
    u = getcent(u, p, getsub(u, p, l));
    cp[u] = p;
    cl[u] = l;
    for (auto [v, c] : adj[u]) {
        if (cl[v]) {
            continue;
        }
        d[l][v] = c;
        build(v, u, l + 1);
    }
}

#define MXST 2 * MAXN + MAXN * 62
int sm[MXST], lc[MXST], rc[MXST], ptr;
void incre(int p, int x, int u, int lo = 0, int hi = INF) {
    if (lo == hi) {
        sm[u] += x;
        return;
    }
    int mid = lo + hi >> 1;
    if (p <= mid) {
        if (!lc[u]) {
            assert(ptr < MXST);
            lc[u] = ptr++;
        }
        incre(p, x, lc[u], lo, mid);
    } else {
        if (!rc[u]) {
            assert(ptr < MXST);
            rc[u] = ptr++;
        }
        incre(p, x, rc[u], mid + 1, hi);
    }
    sm[u] = sm[lc[u]] + sm[rc[u]];
}
int qsm(int s, int e, int u, int lo = 0, int hi = INF) {
    if (u == 0) {
        return 0;
    }
    if (lo >= s && hi <= e) {
        return sm[u];
    }
    int mid = lo + hi >> 1;
    int res = 0;
    if (s <= mid) {
        res += qsm(s, e, lc[u], lo, mid);
    }
    if (e > mid) {
        res += qsm(s, e, rc[u], mid + 1, hi);
    }
    return res;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n;
    REP (i, 1, n) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
        eg[i] = {a, b, c};
    }
    build(1, 0, 1);
    cerr << "------------ CP ARRAY ------------\n";
    REP (i, 1, n + 1) {
        cerr << i << ": " << cp[i] << '\n';
    }
    cerr << "----------------------------------\n";
    cin >> q;
    ptr = 2 * n + 5;
    while (q--) {
        char c; cin >> c;
        if (c == '+') {
            int x, r; cin >> x >> r;
            cerr << "+ " << x << ' ' << r << '\n';
            int ox = x;
            RREP (l, cl[x], 1) {
                ll tr = r - d[l][ox];
                if (tr >= 0) {
                    incre(tr, 1, x << 1);
                    cerr << "NORM UPDATE: " << tr << ' ' << x << '\n';
                }
                if (l > 1) {
                    ll tr = r - d[l - 1][ox];
                    if (tr >= 0) {
                        incre(tr, 1, x << 1 ^ 1);
                        cerr << "WEIRD UPDATE: " << tr << ' ' << x << '\n';
                    }
                }
                x = cp[x];
            }
            //assert(x == 0);
        } else {
            int y; cin >> y;
            auto [u, v, c] = eg[y];
            if (cl[u] < cl[v]) {
                swap(u, v);
            }
            cerr << "? " << u << ' ' << v << '\n';
            int ou = u, ov = v;
            int pu = -1;
            int ans = 0;
            RREP (l, cl[u], cl[v] + 1) {
                ll nd = d[l][ou] + c;
                if (nd <= INF) {
                    int res = qsm(nd, INF, u << 1);
                    ans += res;
                    cerr << "NORM QRY: " << nd << ' ' << u << " -> " << res << '\n';
                    if (pu != -1) {
                        res = qsm(nd, INF, pu << 1 ^ 1);
                        ans -= res;
                        cerr << "WEIRD QRY: " << nd << ' ' << u << " -> " << res << '\n';
                    }
                }
                pu = u;
                u = cp[u];
            }
            //assert(u == v);
            RREP (l, cl[v], 1) {
                ll nd = max(d[l][ou], d[l][ov]);
                if (nd <= INF) {
                    int res = qsm(nd, INF, u << 1);
                    ans += res;
                    cerr << "NORM QRY: " << nd << ' ' << u << " -> " << res << '\n';
                    //assert(pu != -1);
                    res = qsm(nd, INF, pu << 1 ^ 1);
                    ans -= res;
                    cerr << "WEIRD QRY: " << nd << ' ' << u << " -> " << res << '\n';
                }
                pu = u;
                u = cp[u];
            }
            //assert(u == 0);
            cout << ans << '\n';
        }
    }
    return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

100000
2670 75097 4080
87477 75802 1712
51835 36626 2883
19412 25923 5852
23976 19312 2520
82536 19514 2492
27160 66601 4483
99087 15088 3504
47050 58820 2964
37063 5696 9901
7717 1496 4891
79136 5448 4340
22575 81285 9289
96280 3803 9877
41980 32139 2855
44236 64938 3298
5983 99947 9666
95856 62545...

output:

0
0
0
2
2
5
2
2
3
4
4
7
8
9
11
10
14
12
12
10
11
10
10
9
10
11
11
9
15
11
14
13
14
16
11
17
15
13
15
14
14
20
15
20
22
22
20
17
23
23
24
29
24
26
30
31
36
28
37
39
35
34
45
39
46
45
43
46
42
49
44
50
43
47
52
50
49
57
51
56
61
58
68
66
69
69
61
63
67
63
72
74
78
72
73
78
77
73
85
76
86
82
85
76
82
8...

result: