oj.uz

Submission #594422

# Submission time Handle Problem Language Result Execution time Memory
594422 2022-07-12T12:23:08 Z AA_Surely Designated Cities (JOI19_designated_cities) C++17
23 / 100
 2000 ms 131260 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 2 ms 4948 KB Output is correct
2 Correct 2 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 3 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 2 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
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 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 3 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 2 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 150 ms 6324 KB Output is correct
14 Correct 4 ms 6356 KB Output is correct
15 Correct 141 ms 6348 KB Output is correct
16 Correct 146 ms 6328 KB Output is correct
17 Correct 145 ms 6316 KB Output is correct
18 Correct 152 ms 6312 KB Output is correct
19 Correct 150 ms 6328 KB Output is correct
20 Correct 174 ms 6316 KB Output is correct
21 Correct 141 ms 6328 KB Output is correct
22 Correct 118 ms 6320 KB Output is correct
23 Correct 214 ms 6340 KB Output is correct
24 Correct 638 ms 6376 KB Output is correct
25 Correct 16 ms 6356 KB Output is correct
26 Correct 795 ms 6376 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 2079 ms 131260 KB Time limit exceeded
3 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 2 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 3 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 2 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 Execution timed out 2079 ms 131260 KB Time limit exceeded
14 Halted 0 ms 0 KB -