oj.uz

Submission #594415

# Submission time Handle Problem Language Result Execution time Memory
594415 2022-07-12T12:13:58 Z AA_Surely Designated Cities (JOI19_designated_cities) C++17
22 / 100
 1176 ms 141584 KB 
#include <bits/stdc++.h>

#define FOR(i, x, n)    for(LL i = x; i < n; i++)
#define F0R(i, n)       FOR(i, 0, n)
#define ROF(i, x, n)    for(LL 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<LL, LL>    PLL;

typedef vector<LL>      VLL;
typedef vector<PLL>     VPLL;

const int N = 2e5 + 7;
const LL INF = 1e17 + 10;
const int LOG = 22;

#define U 1
#define D 2

#define lc now << 1
#define rc now << 1 | 1
#define endl '\n'

LL 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];
VPLL adj[N];
VLL ord;

void init() {
    cin >> n;
    F0R(i, n - 1) {
        LL 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) {
            LL x; cin >> x;
            if (x == 2) cout << 0 << endl;
            else cout << min(eset[0][2], eset[0][3]) << endl;
        }

        exit(0);
    }

    return;
}

void dfs(LL now, LL sm, LL 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(LL v, LL x, LL 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 LL lca(LL a, LL 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(LL id, LL val, LL now = 1, LL ls = 0, LL rs = l - 1) {
    if (ls == rs) {
        tree[now] = val;
        return;
    }

    LL 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;
}

LL rightest(LL rq, LL now = 1, LL ls = 0, LL rs = l - 1) {
    if (ls >= rq || !tree[now]) return -1;
    if (ls == rs) return ls;
    LL mid = (ls + rs) >> 1;
    LL case1 = rightest(rq, rc, mid + 1, rs);
    return (case1 != -1 ? case1 : rightest(rq, lc, ls, mid));
}

LL leftest(LL lq, LL now = 1, LL ls = 0, LL rs = l - 1) {
    if (rs <= lq || !tree[now]) return l;
    if (ls == rs) return ls;
    LL mid = (ls + rs) >> 1;
    LL case1 = leftest(lq, lc, ls, mid);
    return (case1 != l ? case1 : leftest(lq, rc, mid + 1, rs));
}

void segc(LL id, LL val, LL now = 1, LL ls = 0, LL rs = l - 1) {
    if (ls == rs) {
        seg[now] = val;
        return;
    }

    LL 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(LL now = 1, LL ls = 0, LL rs = l - 1) {
    if (ls == rs) return {ls, seg[now]};
    LL mid = (ls + rs) >> 1;
    if (seg[lc] <= seg[rc]) return descend(lc, ls, mid);
    return descend(rc, mid + 1, rs);
}

LL calc(LL x) {
    LL lft = rightest(x);
    LL rgt = leftest(x);
    if (lft == -1) {
        LL rmost = rightest(l);
        LL x_rmost = lca(ord[x], ord[rmost]);
        LL rgt_rmost = lca(ord[rgt], ord[rmost]);
        LL 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) {
        LL lmost = leftest(-1);
        LL lmost_x = lca(ord[lmost], ord[x]);
        LL lft_x = lca(ord[lft], ord[x]);
        LL 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);
    }

    LL xx = lca(ord[lft], ord[x]);
    LL yy = lca(ord[x], ord[rgt]); 
    LL zz = (height[xx] >= height[yy] ? xx : yy);

    return lift(ord[x], height[ ord[x] ] - height[zz], D);
}

void rem(LL x) {
    LL lft = rightest(x);
    LL rgt = leftest(x);

    change(x, 0);
    segc(x, INF);
    if (lft != -1) {
        LL tmp = calc(lft);
        segc(lft, tmp);
    }

    if (rgt != l) {
        LL tmp = calc(rgt);
        segc(rgt, 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;
    }

    while(q--) {
        LL x; cin >> x;
        cout << ans[x] << endl;
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 3 ms 5028 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 739 ms 131928 KB Output is correct
3 Correct 327 ms 139448 KB Output is correct
4 Correct 605 ms 131976 KB Output is correct
5 Correct 837 ms 132032 KB Output is correct
6 Correct 756 ms 133924 KB Output is correct
7 Correct 887 ms 133112 KB Output is correct
8 Correct 395 ms 140524 KB Output is correct
9 Correct 1176 ms 139064 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 777 ms 131984 KB Output is correct
3 Correct 328 ms 141412 KB Output is correct
4 Correct 584 ms 131932 KB Output is correct
5 Correct 764 ms 132204 KB Output is correct
6 Correct 760 ms 134208 KB Output is correct
7 Correct 1096 ms 138948 KB Output is correct
8 Correct 655 ms 138220 KB Output is correct
9 Correct 1153 ms 139124 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 3 ms 5028 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Incorrect 6 ms 6228 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 739 ms 131928 KB Output is correct
3 Correct 327 ms 139448 KB Output is correct
4 Correct 605 ms 131976 KB Output is correct
5 Correct 837 ms 132032 KB Output is correct
6 Correct 756 ms 133924 KB Output is correct
7 Correct 887 ms 133112 KB Output is correct
8 Correct 395 ms 140524 KB Output is correct
9 Correct 1176 ms 139064 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 777 ms 131984 KB Output is correct
12 Correct 328 ms 141412 KB Output is correct
13 Correct 584 ms 131932 KB Output is correct
14 Correct 764 ms 132204 KB Output is correct
15 Correct 760 ms 134208 KB Output is correct
16 Correct 1096 ms 138948 KB Output is correct
17 Correct 655 ms 138220 KB Output is correct
18 Correct 1153 ms 139124 KB Output is correct
19 Correct 3 ms 4920 KB Output is correct
20 Correct 757 ms 131928 KB Output is correct
21 Correct 380 ms 141584 KB Output is correct
22 Correct 588 ms 131948 KB Output is correct
23 Incorrect 750 ms 132248 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 3 ms 5028 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 739 ms 131928 KB Output is correct
14 Correct 327 ms 139448 KB Output is correct
15 Correct 605 ms 131976 KB Output is correct
16 Correct 837 ms 132032 KB Output is correct
17 Correct 756 ms 133924 KB Output is correct
18 Correct 887 ms 133112 KB Output is correct
19 Correct 395 ms 140524 KB Output is correct
20 Correct 1176 ms 139064 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 777 ms 131984 KB Output is correct
23 Correct 328 ms 141412 KB Output is correct
24 Correct 584 ms 131932 KB Output is correct
25 Correct 764 ms 132204 KB Output is correct
26 Correct 760 ms 134208 KB Output is correct
27 Correct 1096 ms 138948 KB Output is correct
28 Correct 655 ms 138220 KB Output is correct
29 Correct 1153 ms 139124 KB Output is correct
30 Correct 3 ms 4948 KB Output is correct
31 Incorrect 6 ms 6228 KB Output isn't correct
32 Halted 0 ms 0 KB -