oj.uz

답안 #594428

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594428 2022-07-12T12:30:39 Z AA_Surely Designated Cities (JOI19_designated_cities) C++17
100 / 100
 1296 ms 138612 KB 
#include <bits/stdc++.h>
 
#define FOR(i, x, n)    for(int i = x; i < n; i++)
#define F0R(i, n)       FOR(i, 0, n)
#define ROF(i, x, n)    for(int i = n - 1; i >= x; i--)
#define R0F(i, n)       ROF(i, 0, n)
 
#define WTF             cout << "WTF" << endl;
 
#define IOS             ios_base::sync_with_stdio(0); cin.tie(0);
#define F               first
#define S               second
#define pb              push_back
 
#define ALL(x)          x.begin(), x.end()
#define RALL(x)         x.rbegin(), x.rend()
 
using namespace std;
 
typedef long long       LL;
 
typedef pair<int, int>  PII;
typedef pair<LL, LL>    PLL;
 
typedef vector<int>     VI;
typedef vector<LL>      VLL;
typedef vector<PII>     VPII;
typedef vector<PLL>     VPLL;
 
const int N = 2e5 + 7;
const LL INF = 1e18 + 7;
const int LOG = 22;
 
#define U 1
#define D 2
 
#define lc now << 1
#define rc now << 1 | 1
#define endl '\n'
 
int n, q, r, l;
LL eset[N][4], height[N], up[N][LOG][3];
LL tree[N << 2], seg[N << 2], ans[N];
bool exist[N];
VPII adj[N];
VI ord;
 
void init() {
    cin >> n;
    F0R(i, n - 1) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        adj[--u].pb({--v, i});
        adj[v].pb({u, i});
 
        eset[i][0] = u; eset[i][1] = v; 
        eset[i][2] = a; eset[i][3] = b;
    }
 
    cin >> q;
    return;
}
 
void corner() {
    if (n == 2) {
        F0R(i, q) {
            int x; cin >> x;
            if (x == 2) cout << 0 << endl;
            else cout << min(eset[0][2], eset[0][3]) << endl;
        }
 
        exit(0);
    }
 
    return;
}
 
void dfs(int now, LL sm, int par = n) {
    ans[1] = min(ans[1], sm);
 
    if (adj[now].size() == 1) {
        ord.pb(now);
        l++;
    }
 
    for(const auto &[on, id] : adj[now]) if (on != par) {
        up[on][0][0] = now;
        up[on][0][U] = eset[id][2];
        up[on][0][D] = eset[id][3];
        if (eset[id][0] == now) swap(up[on][0][U], up[on][0][D]);
 
        height[on] = height[now] + 1;
 
        dfs(on, sm + up[on][0][U] - up[on][0][D], now);
    }
 
    return;
}
 
void precalc() {
    up[r][0][0] = up[n][0][0] = n;
 
    FOR(k, 1, LOG) F0R(i, n + 1) {
        up[i][k][0] = up[ up[i][k - 1][0] ][k - 1][0];
        up[i][k][1] = up[i][k - 1][1] + up[ up[i][k - 1][0] ][k - 1][1];
        up[i][k][2] = up[i][k - 1][2] + up[ up[i][k - 1][0] ][k - 1][2];
    }
 
    return;
}
 
inline LL lift(int v, int x, int ask) {
    LL su = 0, sd = 0;
    F0R(i, LOG) if ((x >> i) & 1) {
        su += up[v][i][U];
        sd += up[v][i][D];
        v = up[v][i][0];
    }
 
    if (!ask) return v;
    if (ask == U) return su;
    return sd;
}
 
inline int lca(int a, int b) {
    if (height[a] < height[b]) swap(a, b);
    a = lift(a, height[a] - height[b], 0);
    if (a == b) return a;
    R0F(i, LOG) if (up[a][i][0] != up[b][i][0]) 
        a = up[a][i][0], b = up[b][i][0];
 
    return up[a][0][0];
}
 
void change(int id, LL val, int now = 1, int ls = 0, int rs = l - 1) {
    if (ls == rs) {
        tree[now] = val;
        return;
    }
 
    int mid = (ls + rs) >> 1;
    if (id <= mid) change(id, val, lc, ls, mid);
    else change(id, val, rc, mid + 1, rs);
 
    tree[now] = tree[lc] + tree[rc];
    return;
}
 
int rightest(int rq, int now = 1, int ls = 0, int rs = l - 1) {
    if (ls >= rq || !tree[now]) return -1;
    if (ls == rs) return ls;
    int mid = (ls + rs) >> 1;
    int case1 = rightest(rq, rc, mid + 1, rs);
    return (case1 != -1 ? case1 : rightest(rq, lc, ls, mid));
}
 
int leftest(int lq, int now = 1, int ls = 0, int rs = l - 1) {
    if (rs <= lq || !tree[now]) return l;
    if (ls == rs) return ls;
    int mid = (ls + rs) >> 1;
    int case1 = leftest(lq, lc, ls, mid);
    return (case1 != l ? case1 : leftest(lq, rc, mid + 1, rs));
}
 
void segc(int id, LL val, int now = 1, int ls = 0, int rs = l - 1) {
    if (ls == rs) {
        seg[now] = val;
        return;
    }
 
    int mid = (ls + rs) >> 1;
    if (id <= mid) segc(id, val, lc, ls, mid);
    else segc(id, val, rc, mid + 1, rs);
 
    seg[now] = min(seg[lc], seg[rc]);
    return;
}
 
PLL descend(int now = 1, int ls = 0, int rs = l - 1) {
    if (ls == rs) return {ls, seg[now]};
    int mid = (ls + rs) >> 1;
    if (seg[lc] <= seg[rc]) return descend(lc, ls, mid);
    return descend(rc, mid + 1, rs);
}
 
LL calc(int x) {
    int lft = rightest(x);
    int rgt = leftest(x);
    if (lft == -1) {
        int rmost = rightest(l);
        int x_rmost = lca(ord[x], ord[rmost]);
        int rgt_rmost = lca(ord[rgt], ord[rmost]);
        int x_rgt = lca(ord[x], ord[rgt]);
        
        return lift(ord[x], height[ ord[x] ] - height[x_rgt], D) + lift(rgt_rmost, height[rgt_rmost] - height[x_rmost], U);
    }
 
    if (rgt == l) {
        int lmost = leftest(-1);
        int lmost_x = lca(ord[lmost], ord[x]);
        int lft_x = lca(ord[lft], ord[x]);
        int lmost_lft = lca(ord[lmost], ord[lft]);
 
        return lift(ord[x], height[ ord[x] ] - height[lft_x], D) + lift(lmost_lft, height[lmost_lft] - height[lmost_x], U);
    }
 
    int xx = lca(ord[lft], ord[x]);
    int yy = lca(ord[x], ord[rgt]); 
    int zz = (height[xx] >= height[yy] ? xx : yy);
 
    return lift(ord[x], height[ ord[x] ] - height[zz], D);
}
 
void rem(int x) {
    change(x, 0);
    segc(x, INF);

    int lft = rightest(x);
    int rgt = leftest(x);
    int lmost = leftest(-1);
    int rmost = rightest(l);

    if (lft != -1) {
        LL tmp = calc(lft);
        segc(lft, tmp);
    }
 
    if (rgt != l) {
        LL tmp = calc(rgt);
        segc(rgt, tmp);
    }

    LL tmp = calc(rmost);
    segc(rmost, tmp);

    tmp = calc(lmost);
    segc(lmost, tmp);
 
    return;
}
 
int main() {
    IOS;
 
    init();
    corner();
 
    ans[1] = INF;
    R0F(i, n) if (adj[i].size() > 1) r = i;
 
    dfs(r, 0);
 
    LL smm = 0;
    F0R(i, n) smm += up[i][0][D];
    ans[1] += smm;
 
    precalc();
 
    F0R(i, l) change(i, 1);
    F0R(i, l) {
        LL val = calc(i);
        segc(i, val);
    }
 
    fill(exist, exist + l, 1);
    ROF(b, 3, l + 1) {
        PLL opt = descend();
        ans[b - 1] = ans[b] + opt.S;
        rem(opt.F);
        exist[opt.F] = 0;
        
        /*F0R(i, l) if (exist[i]) {
            segc(i, calc(i));
        }*/
    }
 
    while(q--) {
        int x; cin >> x;
        cout << ans[x] << endl;
    }
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 761 ms 128708 KB Output is correct
3 Correct 316 ms 135168 KB Output is correct
4 Correct 620 ms 128800 KB Output is correct
5 Correct 804 ms 128836 KB Output is correct
6 Correct 784 ms 130492 KB Output is correct
7 Correct 949 ms 129936 KB Output is correct
8 Correct 367 ms 136412 KB Output is correct
9 Correct 1247 ms 135728 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 759 ms 128832 KB Output is correct
3 Correct 302 ms 137292 KB Output is correct
4 Correct 634 ms 128804 KB Output is correct
5 Correct 811 ms 128968 KB Output is correct
6 Correct 799 ms 130828 KB Output is correct
7 Correct 1188 ms 135432 KB Output is correct
8 Correct 626 ms 134312 KB Output is correct
9 Correct 1283 ms 135740 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 8 ms 6228 KB Output is correct
14 Correct 7 ms 6228 KB Output is correct
15 Correct 9 ms 6296 KB Output is correct
16 Correct 7 ms 6228 KB Output is correct
17 Correct 7 ms 6228 KB Output is correct
18 Correct 7 ms 6228 KB Output is correct
19 Correct 7 ms 6228 KB Output is correct
20 Correct 7 ms 6356 KB Output is correct
21 Correct 6 ms 6228 KB Output is correct
22 Correct 6 ms 6228 KB Output is correct
23 Correct 8 ms 6228 KB Output is correct
24 Correct 9 ms 6356 KB Output is correct
25 Correct 5 ms 6356 KB Output is correct
26 Correct 9 ms 6352 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 761 ms 128708 KB Output is correct
3 Correct 316 ms 135168 KB Output is correct
4 Correct 620 ms 128800 KB Output is correct
5 Correct 804 ms 128836 KB Output is correct
6 Correct 784 ms 130492 KB Output is correct
7 Correct 949 ms 129936 KB Output is correct
8 Correct 367 ms 136412 KB Output is correct
9 Correct 1247 ms 135728 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 759 ms 128832 KB Output is correct
12 Correct 302 ms 137292 KB Output is correct
13 Correct 634 ms 128804 KB Output is correct
14 Correct 811 ms 128968 KB Output is correct
15 Correct 799 ms 130828 KB Output is correct
16 Correct 1188 ms 135432 KB Output is correct
17 Correct 626 ms 134312 KB Output is correct
18 Correct 1283 ms 135740 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 764 ms 128712 KB Output is correct
21 Correct 318 ms 137472 KB Output is correct
22 Correct 641 ms 128780 KB Output is correct
23 Correct 779 ms 128848 KB Output is correct
24 Correct 732 ms 128800 KB Output is correct
25 Correct 774 ms 128936 KB Output is correct
26 Correct 767 ms 128832 KB Output is correct
27 Correct 814 ms 129056 KB Output is correct
28 Correct 749 ms 130116 KB Output is correct
29 Correct 782 ms 128588 KB Output is correct
30 Correct 860 ms 129164 KB Output is correct
31 Correct 1012 ms 133832 KB Output is correct
32 Correct 712 ms 134800 KB Output is correct
33 Correct 1296 ms 135832 KB Output is correct

Subtask #6
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 761 ms 128708 KB Output is correct
14 Correct 316 ms 135168 KB Output is correct
15 Correct 620 ms 128800 KB Output is correct
16 Correct 804 ms 128836 KB Output is correct
17 Correct 784 ms 130492 KB Output is correct
18 Correct 949 ms 129936 KB Output is correct
19 Correct 367 ms 136412 KB Output is correct
20 Correct 1247 ms 135728 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 759 ms 128832 KB Output is correct
23 Correct 302 ms 137292 KB Output is correct
24 Correct 634 ms 128804 KB Output is correct
25 Correct 811 ms 128968 KB Output is correct
26 Correct 799 ms 130828 KB Output is correct
27 Correct 1188 ms 135432 KB Output is correct
28 Correct 626 ms 134312 KB Output is correct
29 Correct 1283 ms 135740 KB Output is correct
30 Correct 2 ms 4948 KB Output is correct
31 Correct 8 ms 6228 KB Output is correct
32 Correct 7 ms 6228 KB Output is correct
33 Correct 9 ms 6296 KB Output is correct
34 Correct 7 ms 6228 KB Output is correct
35 Correct 7 ms 6228 KB Output is correct
36 Correct 7 ms 6228 KB Output is correct
37 Correct 7 ms 6228 KB Output is correct
38 Correct 7 ms 6356 KB Output is correct
39 Correct 6 ms 6228 KB Output is correct
40 Correct 6 ms 6228 KB Output is correct
41 Correct 8 ms 6228 KB Output is correct
42 Correct 9 ms 6356 KB Output is correct
43 Correct 5 ms 6356 KB Output is correct
44 Correct 9 ms 6352 KB Output is correct
45 Correct 3 ms 4948 KB Output is correct
46 Correct 764 ms 128712 KB Output is correct
47 Correct 318 ms 137472 KB Output is correct
48 Correct 641 ms 128780 KB Output is correct
49 Correct 779 ms 128848 KB Output is correct
50 Correct 732 ms 128800 KB Output is correct
51 Correct 774 ms 128936 KB Output is correct
52 Correct 767 ms 128832 KB Output is correct
53 Correct 814 ms 129056 KB Output is correct
54 Correct 749 ms 130116 KB Output is correct
55 Correct 782 ms 128588 KB Output is correct
56 Correct 860 ms 129164 KB Output is correct
57 Correct 1012 ms 133832 KB Output is correct
58 Correct 712 ms 134800 KB Output is correct
59 Correct 1296 ms 135832 KB Output is correct
60 Correct 3 ms 4948 KB Output is correct
61 Correct 802 ms 130172 KB Output is correct
62 Correct 337 ms 135608 KB Output is correct
63 Correct 682 ms 130340 KB Output is correct
64 Correct 800 ms 130224 KB Output is correct
65 Correct 785 ms 130004 KB Output is correct
66 Correct 803 ms 130108 KB Output is correct
67 Correct 796 ms 130048 KB Output is correct
68 Correct 856 ms 130348 KB Output is correct
69 Correct 779 ms 131716 KB Output is correct
70 Correct 692 ms 129828 KB Output is correct
71 Correct 858 ms 130596 KB Output is correct
72 Correct 959 ms 135544 KB Output is correct
73 Correct 665 ms 134480 KB Output is correct
74 Correct 1287 ms 138612 KB Output is correct