oj.uz

Submission #594412

# Submission time Handle Problem Language Result Execution time Memory
594412 2022-07-12T12:11:18 Z AA_Surely Designated Cities (JOI19_designated_cities) C++17
22 / 100
 1079 ms 154048 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<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'

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

LL 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;
    LL case1 = rightest(rq, rc, mid + 1, rs);
    return (case1 != -1 ? case1 : rightest(rq, lc, ls, mid));
}

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

    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) {
    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--) {
        int x; cin >> x;
        cout << ans[x] << endl;
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 669 ms 131948 KB Output is correct
3 Correct 357 ms 150796 KB Output is correct
4 Correct 543 ms 136892 KB Output is correct
5 Correct 755 ms 138416 KB Output is correct
6 Correct 732 ms 141124 KB Output is correct
7 Correct 805 ms 139448 KB Output is correct
8 Correct 402 ms 152092 KB Output is correct
9 Correct 1027 ms 145548 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 692 ms 131868 KB Output is correct
3 Correct 345 ms 153840 KB Output is correct
4 Correct 579 ms 136960 KB Output is correct
5 Correct 680 ms 138556 KB Output is correct
6 Correct 693 ms 141520 KB Output is correct
7 Correct 943 ms 145248 KB Output is correct
8 Correct 581 ms 147632 KB Output is correct
9 Correct 1079 ms 145240 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 5076 KB Output is correct
5 Correct 4 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 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 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 3 ms 4948 KB Output is correct
2 Correct 669 ms 131948 KB Output is correct
3 Correct 357 ms 150796 KB Output is correct
4 Correct 543 ms 136892 KB Output is correct
5 Correct 755 ms 138416 KB Output is correct
6 Correct 732 ms 141124 KB Output is correct
7 Correct 805 ms 139448 KB Output is correct
8 Correct 402 ms 152092 KB Output is correct
9 Correct 1027 ms 145548 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 692 ms 131868 KB Output is correct
12 Correct 345 ms 153840 KB Output is correct
13 Correct 579 ms 136960 KB Output is correct
14 Correct 680 ms 138556 KB Output is correct
15 Correct 693 ms 141520 KB Output is correct
16 Correct 943 ms 145248 KB Output is correct
17 Correct 581 ms 147632 KB Output is correct
18 Correct 1079 ms 145240 KB Output is correct
19 Correct 3 ms 5020 KB Output is correct
20 Correct 712 ms 138372 KB Output is correct
21 Correct 386 ms 154048 KB Output is correct
22 Correct 729 ms 137012 KB Output is correct
23 Incorrect 689 ms 138680 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 5076 KB Output is correct
5 Correct 4 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 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 669 ms 131948 KB Output is correct
14 Correct 357 ms 150796 KB Output is correct
15 Correct 543 ms 136892 KB Output is correct
16 Correct 755 ms 138416 KB Output is correct
17 Correct 732 ms 141124 KB Output is correct
18 Correct 805 ms 139448 KB Output is correct
19 Correct 402 ms 152092 KB Output is correct
20 Correct 1027 ms 145548 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 692 ms 131868 KB Output is correct
23 Correct 345 ms 153840 KB Output is correct
24 Correct 579 ms 136960 KB Output is correct
25 Correct 680 ms 138556 KB Output is correct
26 Correct 693 ms 141520 KB Output is correct
27 Correct 943 ms 145248 KB Output is correct
28 Correct 581 ms 147632 KB Output is correct
29 Correct 1079 ms 145240 KB Output is correct
30 Correct 4 ms 4948 KB Output is correct
31 Incorrect 6 ms 6228 KB Output isn't correct
32 Halted 0 ms 0 KB -