oj.uz

Submission #594420

# Submission time Handle Problem Language Result Execution time Memory
594420 2022-07-12T12:21:47 Z AA_Surely Designated Cities (JOI19_designated_cities) C++17
22 / 100
 1138 ms 141572 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 = 1e15 + 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 2 ms 5024 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 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 754 ms 131912 KB Output is correct
3 Correct 353 ms 139440 KB Output is correct
4 Correct 573 ms 132008 KB Output is correct
5 Correct 786 ms 132132 KB Output is correct
6 Correct 778 ms 134048 KB Output is correct
7 Correct 886 ms 132948 KB Output is correct
8 Correct 400 ms 140484 KB Output is correct
9 Correct 1138 ms 139168 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 795 ms 131936 KB Output is correct
3 Correct 342 ms 141424 KB Output is correct
4 Correct 584 ms 131924 KB Output is correct
5 Correct 790 ms 132024 KB Output is correct
6 Correct 747 ms 134212 KB Output is correct
7 Correct 1111 ms 138936 KB Output is correct
8 Correct 657 ms 137924 KB Output is correct
9 Correct 1121 ms 139168 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 2 ms 5024 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 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 8 ms 6244 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 754 ms 131912 KB Output is correct
3 Correct 353 ms 139440 KB Output is correct
4 Correct 573 ms 132008 KB Output is correct
5 Correct 786 ms 132132 KB Output is correct
6 Correct 778 ms 134048 KB Output is correct
7 Correct 886 ms 132948 KB Output is correct
8 Correct 400 ms 140484 KB Output is correct
9 Correct 1138 ms 139168 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 795 ms 131936 KB Output is correct
12 Correct 342 ms 141424 KB Output is correct
13 Correct 584 ms 131924 KB Output is correct
14 Correct 790 ms 132024 KB Output is correct
15 Correct 747 ms 134212 KB Output is correct
16 Correct 1111 ms 138936 KB Output is correct
17 Correct 657 ms 137924 KB Output is correct
18 Correct 1121 ms 139168 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 769 ms 131984 KB Output is correct
21 Correct 372 ms 141572 KB Output is correct
22 Correct 632 ms 131972 KB Output is correct
23 Incorrect 753 ms 132256 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 2 ms 5024 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 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 754 ms 131912 KB Output is correct
14 Correct 353 ms 139440 KB Output is correct
15 Correct 573 ms 132008 KB Output is correct
16 Correct 786 ms 132132 KB Output is correct
17 Correct 778 ms 134048 KB Output is correct
18 Correct 886 ms 132948 KB Output is correct
19 Correct 400 ms 140484 KB Output is correct
20 Correct 1138 ms 139168 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 795 ms 131936 KB Output is correct
23 Correct 342 ms 141424 KB Output is correct
24 Correct 584 ms 131924 KB Output is correct
25 Correct 790 ms 132024 KB Output is correct
26 Correct 747 ms 134212 KB Output is correct
27 Correct 1111 ms 138936 KB Output is correct
28 Correct 657 ms 137924 KB Output is correct
29 Correct 1121 ms 139168 KB Output is correct
30 Correct 3 ms 4948 KB Output is correct
31 Incorrect 8 ms 6244 KB Output isn't correct
32 Halted 0 ms 0 KB -