oj.uz

Submission #424904

# Submission time Handle Problem Language Result Execution time Memory
424904 2021-06-12T11:26:01 Z Hideo Designated Cities (JOI19_designated_cities) C++17
23 / 100
 2000 ms 63984 KB 
#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) {
        cout << "wtf" << endl;
        exit(0);
    }
    if (l == r){
        t[v] = {dis(lc, a[l]), l};
        return;
    }
    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;
        }
    }
}

int negr, negr2;

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;
        negr = c;
        negr2 = d;
        g[a].pb({b, {c, d}});
        g[b].pb({a, {d, c}});
        s += c + d;
    }
    if (n == 2){
        ans[1] = max(negr, negr2);
        ans[2] = s;
        int q;
        cin >> q;
        for (int i = 1; i <= q; i++){
            int e;
            cin >> e;
            cout << s - ans[e] << endl;
        }
        return 0;
    }
    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);
    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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 5 ms 5024 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5088 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Execution timed out 2080 ms 61948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 5 ms 5024 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5088 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 36 ms 5840 KB Output is correct
14 Correct 10 ms 5836 KB Output is correct
15 Correct 31 ms 5824 KB Output is correct
16 Correct 31 ms 5828 KB Output is correct
17 Correct 36 ms 5700 KB Output is correct
18 Correct 26 ms 5840 KB Output is correct
19 Correct 32 ms 5832 KB Output is correct
20 Correct 28 ms 5836 KB Output is correct
21 Correct 29 ms 5720 KB Output is correct
22 Correct 22 ms 5840 KB Output is correct
23 Correct 38 ms 5812 KB Output is correct
24 Correct 64 ms 5828 KB Output is correct
25 Correct 14 ms 5836 KB Output is correct
26 Correct 73 ms 5816 KB Output is correct

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 5 ms 5024 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5088 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Execution timed out 2050 ms 63984 KB Time limit exceeded
14 Halted 0 ms 0 KB -