oj.uz

답안 #594425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594425 2022-07-12T12:25:48 Z AA_Surely Designated Cities (JOI19_designated_cities) C++17
7 / 100
 1273 ms 145852 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);
    LL lmost = leftest(-1);
    LL rmost = rightest(l);
 
    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);
    }

    LL tmp = calc(rmost);
    segc(rmost, tmp);

    tmp = calc(lmost);
    segc(lmost, 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
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 792 ms 132084 KB Output is correct
3 Correct 334 ms 144328 KB Output is correct
4 Correct 634 ms 131972 KB Output is correct
5 Correct 821 ms 132136 KB Output is correct
6 Correct 797 ms 134696 KB Output is correct
7 Correct 932 ms 133060 KB Output is correct
8 Correct 419 ms 145852 KB Output is correct
9 Correct 1273 ms 139208 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 803 ms 132008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 792 ms 132084 KB Output is correct
3 Correct 334 ms 144328 KB Output is correct
4 Correct 634 ms 131972 KB Output is correct
5 Correct 821 ms 132136 KB Output is correct
6 Correct 797 ms 134696 KB Output is correct
7 Correct 932 ms 133060 KB Output is correct
8 Correct 419 ms 145852 KB Output is correct
9 Correct 1273 ms 139208 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Incorrect 803 ms 132008 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -