oj.uz

Submission #594410

# Submission time Handle Problem Language Result Execution time Memory
594410 2022-07-12T12:10:53 Z AA_Surely Designated Cities (JOI19_designated_cities) C++17
23 / 100
 2000 ms 137716 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;
        
        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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 6 ms 5084 KB Output is correct
7 Correct 3 ms 5024 KB Output is correct
8 Correct 3 ms 5024 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 3 ms 5028 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2057 ms 137648 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2070 ms 137716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 6 ms 5084 KB Output is correct
7 Correct 3 ms 5024 KB Output is correct
8 Correct 3 ms 5024 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 3 ms 5028 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 236 ms 6384 KB Output is correct
14 Correct 5 ms 6404 KB Output is correct
15 Correct 157 ms 6360 KB Output is correct
16 Correct 211 ms 6384 KB Output is correct
17 Correct 150 ms 6376 KB Output is correct
18 Correct 178 ms 6380 KB Output is correct
19 Correct 185 ms 6388 KB Output is correct
20 Correct 220 ms 6384 KB Output is correct
21 Correct 142 ms 6412 KB Output is correct
22 Correct 146 ms 6396 KB Output is correct
23 Correct 237 ms 6392 KB Output is correct
24 Correct 734 ms 6436 KB Output is correct
25 Correct 40 ms 6484 KB Output is correct
26 Correct 1038 ms 6428 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2057 ms 137648 KB Time limit exceeded
3 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 4 ms 5028 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 6 ms 5084 KB Output is correct
7 Correct 3 ms 5024 KB Output is correct
8 Correct 3 ms 5024 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 3 ms 5028 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Execution timed out 2057 ms 137648 KB Time limit exceeded
14 Halted 0 ms 0 KB -