Submission #424749

#	Time	Username	Problem	Language	Result	Execution time	Memory
424749		Hideo	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	2070 ms	64592 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 bb[N];

int p[N][20], h[N], d[N], nega[N];
int tin[N], tout[N], tim;
int ans[N], sub[2][N];
int n, rt, s;

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

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

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){
            nega[to.fr] = nega[v] + to.sc.fr;
            h[to.fr] = h[v] + to.sc.fr - to.sc.sc;
            dfs(to.fr, v);
            sub[0][v] += sub[0][to.fr] + to.sc.sc;
            sub[1][v] += sub[1][to.fr] + to.sc.fr;
            lr[v] = {min(lr[to.fr].fr, lr[v].fr), max(lr[to.fr].sc, lr[v].sc)};
        }
    }
    tout[v] = tim;
    if (g[v].size() == 1){
        rv[v] = ++cnt;
        lr[v] = {rv[v], rv[v]};
        a.pb(v);
    }
}

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];
}

void prec (int v, int pr = 0){
    for (auto to : g[v]){
        if (to.fr != pr){
            h[to.fr] = h[v] + to.sc.fr + to.sc.sc;
            if (check(to.fr, a[x]) || check(to.fr, a[y])){
                if (check(z, to.fr)){
                    d[to.fr] = d[v] + to.sc.fr + to.sc.sc;
                    del[to.fr] = 1;
                }
                else {
                    d[to.fr] = d[v] + to.sc.fr;
                }
            }
            else {
                d[to.fr] = d[v] + to.sc.sc;
            }
            prec(to.fr, v);
        }
    }
}

int dis (int v, int u){
    int l = lca(v, u);
    return (h[v] + h[u] - 2 * h[l]) - (d[v] + d[u] - 2 * d[l]);
}

void build (int v, int l, int r){
    if (l > r)
        return;
    if (l == r)
        t[v] = {bb[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 v, int l, int r){
    if (l != r){
        lz[v + v] += lz[v];
        lz[v + v + 1] += lz[v];
    }
    t[v].fr += lz[v];
    lz[v] = 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];
}

//pi get (int v, int l, int r, int ql, int qr){
//    push(v, l, r);
//    if (ql <= l && r <= qr)
//        return t[v];
//    if (r < ql || qr < l)
//        return {-1, 0};
//    int mid = (l + r) >> 1;
//    return max(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
//}

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;
    dfs(rt);
//    cout << rt << endl;
    for (int i = 1; i <= n; i++){
        ans[1] = max(ans[1], sub[0][rt] + h[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 < sub[0][rt] + h[l] + nega[v] + nega[u] - 2 * nega[l]){
                mx = sub[0][rt] + h[l] + nega[v] + nega[u] - 2 * nega[l];
                x = v, y = u;
            }
        }
    }
    ans[2] = mx;
//    cout << x << ' ' << y << endl;
    z = lca(x, y);
    x = rv[x]; y = rv[y];
    if (x > y)
        swap(x, y);
    prec(rt);
    for (int i = 1; i <= cnt; i++){
        bb[i] = dis(a[i], z);
    }
    build(1, 1, cnt);
    del[0] = 1;
    for (int i = 3; i <= cnt; i++){
        int it = t[1].sc, val = t[1].fr;
//        cout << a[it] << ' ' << val << endl;
        ans[i] = ans[i - 1] + val;
        if (lr[z].fr <= it && it <= lr[z].sc){
            int v = a[it];
            while (!del[v]){
                del[v] = 1;
                upd(1, 1, cnt, lr[v].fr, lr[v].sc, -((h[v] - h[p[v][0]]) - (d[v] - d[p[v][0]])));
                v = p[v][0];
            }
        }
        else {
            int nz = lca(z, it);
            int v = z;
            while (v != nz){
                if (lr[v].fr > 1)
                    upd(1, 1, cnt, 1, lr[v].fr - 1, -((h[v] - h[p[v][0]]) - (d[v] - d[p[v][0]])));
                if (lr[v].sc < cnt)
                    upd(1, 1, cnt, lr[v].sc + 1, cnt, -((h[v] - h[p[v][0]]) - (d[v] - d[p[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, -((h[v] - h[p[v][0]]) - (d[v] - d[p[v][0]])));
                v = p[v][0];
            }
        }
    }
//    cout << cnt << endl;
    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:150:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  150 | 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