Submission #594410

#	Time	Username	Problem	Language	Result	Execution time	Memory
594410		AA_Surely	Designated Cities (JOI19_designated_cities)	C++17	23 / 100	2070 ms	137716 KiB

designated_cities

#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 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44