Submission #424848

#	Time	Username	Problem	Language	Result	Execution time	Memory
424848		Hideo	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	322 ms	524292 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define int long long
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define pi pair < int, int >

const int N = 2e5 + 7;
const int INF = 1e9 + 7;

pi t[4 * N];
int lz[4 * N];
int p[N][20], h[2][N], w[N];
int tin[N], tout[N], tim;
int ans[N];
int n, rt, s, s_up;

vector < pair < int, pi > > g[N];

pi lr[N];
int rv[N], del[N], cnt;
vector < int > a;

int lc, x, y;

void dfs (int v, int pr = 0){
    lr[v] = {INF, 0};
    tin[v] = ++tim;
    p[v][0] = pr;
    for (int j = 1; j < 20; j++)
        p[v][j] = p[p[v][j - 1]][j - 1];
    for (auto to : g[v]){
        if (to.fr != pr){
            s_up += to.sc.sc;
            h[0][to.fr] = h[0][v] + to.sc.fr;
            h[1][to.fr] = h[1][v] + to.sc.sc;
            dfs(to.fr, v);
            lr[v].fr = min(lr[v].fr, lr[to.fr].fr);
            lr[v].sc = max(lr[v].sc, lr[to.fr].sc);
        }
    }
    tout[v] = tim;
    if (g[v].size() == 1){
        rv[v] = ++cnt;
        lr[v] = {rv[v], rv[v]};
        a.pb(v);
    }
}

inline bool check (int v, int u){
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int lca (int v, int u){
    if (check(v, u))
        return v;
    if (check(u, v))
        return u;
    for (int j = 19; j >= 0; j--)
        if (p[v][j] && !check(p[v][j], u))
            v = p[v][j];
    return p[v][0];
}

inline int dis (int vv, int uu){
    int pp = lca(vv, uu);
    return h[1][vv] - h[1][pp] + h[0][uu] - h[0][pp];
}

void build (int v, int l, int r){
    if (l == r){
        t[v] = {dis(lc, a[l]), l};
    }
    else {
        int mid = (l + r) >> 1ll;
        build(v + v, l, mid);
        build(v + v + 1, mid + 1, r);
        if (t[v + v].fr > t[v + v + 1].fr)
            t[v] = t[v + v];
        else
            t[v] = t[v + v + 1];
    }
}

inline void push (int vv, int ll, int rr){
    if (ll != rr){
        lz[vv + vv] += lz[vv];
        lz[vv + vv + 1] += lz[vv];
    }
    t[vv].fr += lz[vv];
    lz[vv] = 0;
}

void upd (int v, int l, int r, int ql, int qr, int val){
    push(v, l, r);
    if (ql <= l && r <= qr){
        lz[v] = val;
        push(v, l, r);
        return;
    }
    if (r < ql || qr < l)
        return;
    int mid = (l + r) >> 1ll;
    upd(v + v, l, mid, ql, qr, val);
    upd(v + v + 1, mid + 1, r, ql, qr, val);
    if (t[v + v].fr > t[v + v + 1].fr)
        t[v] = t[v + v];
    else
        t[v] = t[v + v + 1];
}

void prec (int v, int pr = 0){
    for (auto to : g[v]){
        if (to.fr != pr){
            prec(to.fr, v);
            if (check(to.fr, lc))
                w[to.fr] = to.sc.sc;
            else
                w[to.fr] = to.sc.fr;
        }
    }
}

main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    a.pb(0);
    cin >> n;
    for (int i = 1; i < n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        g[a].pb({b, {c, d}});
        g[b].pb({a, {d, c}});
        s += c + d;
    }
    for (int i = 1; i <= n; i++){
        if (g[i].size() > 1){
            rt = i;
            break;
        }
    }
    dfs(rt);
    for (int i = 1; i <= n; i++){
        ans[1] = max(ans[1], s_up - h[1][i] + h[0][i]);
    }
    int mx = 0;
    for (int i = 1; i <= cnt; i++){
        for (int j = i + 1; j <= cnt; j++){
            int v = a[i], u = a[j];
            int l = lca(v, u);
            if (mx < s_up - h[1][l] + h[0][l] + h[0][v] + h[0][u] - 2 * h[0][l]){
                mx = s_up - h[1][l] + h[0][l] + h[0][v] + h[0][u] - 2 * h[0][l];
                x = v, y = u;
            }
        }
    }
    ans[2] = mx;
    lc = lca(x, y);
    prec(rt);
    if (cnt < 1){
        cout << "ok";
    }
    build(1, 1, cnt);
    del[0] = 1;
    del[lc] = 1;
    while (x != lc){
        del[x] = 1;
        upd(1, 1, cnt, lr[x].fr, lr[x].sc, -w[x]);
        w[x] = 0;
        x = p[x][0];
    }
    while (y != lc){
        del[y] = 1;
        upd(1, 1, cnt, lr[y].fr, lr[y].sc, -w[y]);
        w[y] = 0;
        y = p[y][0];
    }
    for (int i = 3; i <= cnt; i++){
        int it = t[1].sc, val = t[1].fr;
        ans[i] = ans[i - 1] + val;
        if (lr[lc].fr <= it && it <= lr[lc].sc){
            int v = a[it];
            while (!del[v]){
                del[v] = 1;
                upd(1, 1, cnt, lr[v].fr, lr[v].sc, -w[v]);
                w[v] = 0;
                v = p[v][0];
            }
        }
        else {
            int nw = lca(lc, a[it]);
            int v = lc;
            while (v != nw){
                if (lr[v].fr > 1)
                    upd(1, 1, cnt, 1, lr[v].fr - 1, -w[v]);
                if (lr[v].sc < cnt)
                    upd(1, 1, cnt, lr[v].sc + 1, cnt, -w[v]);
                w[v] = 0;
                v = p[v][0];
                del[v] = 1;
            }
            v = a[it];
            while (!del[v]){
                del[v] = 1;
                upd(1, 1, cnt, lr[v].fr, lr[v].sc, -w[v]);
                w[v] = 0;
                v = p[v][0];
            }
        }
    }
    for (int i = cnt + 1; i <= n; i++)
        ans[i] = s;
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        int e;
        cin >> e;
        cout << s - ans[e] << endl;
    }
}

Compilation message (stderr)

designated_cities.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main (){
      | ^~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44