oj.uz

Submission #427371

# Submission time Handle Problem Language Result Execution time Memory
427371 2021-06-14T14:38:30 Z Hideo Designated Cities (JOI19_designated_cities) C++17
100 / 100
 1154 ms 98244 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#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[2 * N];
int lz[N];
int p[N][20], h[2][N], w[N];
int tin[N], tout[N], tim;
int ans[N];
int n, rt, sum, s_up;

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

pi lr[N], lg[2][N];
int rv[N], del[N], cnt = -1;
vector < int > a;

int lc, x, y;

void dfs (int v, int pr = 0){
    lg[0][v] = lg[1][v] = {0, v};
    lr[v] = {INF, -INF};
    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);
            if (lg[0][v].fr < lg[0][to.fr].fr + to.sc.fr){
                swap(lg[0][v], lg[1][v]);
                lg[0][v] = {lg[0][to.fr].fr + to.sc.fr, lg[0][to.fr].sc};
            }
            else if (lg[1][v].fr < lg[0][to.fr].fr + to.sc.fr)
                lg[1][v] = {lg[0][to.fr].fr + to.sc.fr, lg[0][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];
}

int hg;

void build(int p) {
  while (p > 1) {
    p >>= 1;
    if (t[p<<1].fr > t[p<<1|1].fr)
        t[p] = t[p<<1];
    else
        t[p] = t[p<<1|1];
    t[p].fr += lz[p];
  }
}

void push(int p) {
  for (int s = hg; s > 0; --s) {
    int i = p >> s;
    if (lz[i] != 0) {

      t[i<<1].fr += lz[i];
      if ((i << 1) < cnt)
        lz[i<<1] += lz[i];

      t[i<<1|1].fr += lz[i];
      if ((i<<1|1) < cnt)
        lz[i<<1|1] += lz[i];
      lz[i] = 0;
    }
  }
}

void upd(int l, int r, int value) {
  l += cnt, r += cnt;
  int l0 = l, r0 = r;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l&1){
        t[l].fr += value;
        if (l < cnt)
            lz[l] += value;
        l++;
    }
    if (r&1){
        t[--r].fr += value;
        if (r < cnt)
            lz[r] += value;
    }
  }
  build(l0);
  build(r0 - 1);
}

pi query(int l, int r) {
  l += cnt, r += cnt;
  push(l);
  push(r - 1);
  pi res = {0, 0};
  for (; l < r; l >>= 1, r >>= 1){
    if (l&1 && res.fr < t[l++].fr){
        res = t[l - 1];
    }
    if (r&1 && res.fr < t[--r].fr){
        res = t[r];
    }
  }
  return res;
}

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;

vector < pi > prs;

void reroot (int v, int pr = 0, pi up = {0, 0}){
    if (up.fr > lg[0][v].fr){
        prs.pb({v, up.sc});
        lg[0][v] = up;
    }
    else
        prs.pb({v, lg[0][v].sc});
    for (auto to : g[v]){
        if (to.fr != pr){
            if (lg[0][v].sc == lg[0][to.fr].sc){
                reroot(to.fr, v, {lg[1][v].fr + to.sc.sc, lg[1][v].sc});
            }
            else {
                reroot(to.fr, v, {lg[0][v].fr + to.sc.sc, lg[0][v].sc});
            }
        }
    }
}

int e[N];

main (){
    ios_base::sync_with_stdio(0);
    cin.tie(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}});
        sum += c + d;
    }
    if (n == 2){
        ans[1] = max(negr, negr2);
        ans[2] = sum;
        int q;
        cin >> q;
        for (int i = 1; i <= q; i++){
            int e;
            cin >> e;
            cout << sum - 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]);
    }
    reroot(rt);
    int mx = 0;
    for (pi it : prs){
        int v = it.fr, u = it.sc;
        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);
    cnt++;
    hg = sizeof(int) * 8 - __builtin_clz(cnt);
    prec(rt);
    for (int i = 0; i < cnt; i++){
        t[cnt + i].sc = i;
    }
    for (int i = 0; i < cnt; i++){
        upd(i, i + 1, dis(lc, a[i]));
    }
    del[0] = 1;
    del[lc] = 1;
    while (x != lc){
        del[x] = 1;
        upd(lr[x].fr, lr[x].sc + 1, -w[x]);
        w[x] = 0;
        x = p[x][0];
    }
    while (y != lc){
        del[y] = 1;
        upd(lr[y].fr, lr[y].sc + 1, -w[y]);
        w[y] = 0;
        y = p[y][0];
    }
    int q, mxq = 0;
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> e[i];
        mxq = max(mxq, e[i]);
    }
    for (int i = 3; i <= min(mxq, cnt - 1); i++){
        pi temp = t[1];
        int it = temp.sc, val = temp.fr;
        ans[i] = ans[i - 1] + val;
//        cout << a[it] << ' ' << val << endl;
        if (lr[lc].fr <= it && it <= lr[lc].sc){
            int v = a[it];
            while (!del[v]){
                del[v] = 1;
                upd(lr[v].fr, lr[v].sc + 1, -w[v]);
//                cout << v << ' ' << lr[v].fr << ' ' << lr[v].sc << ' ' << w[v] << endl;
                w[v] = 0;
                v = p[v][0];
            }
        }
        else {
            int v = lc;
            while (!check(v, a[it])){
                if (lr[v].fr > 0){
                    upd(0, lr[v].fr, -w[v]);
//                    cout << v << ' ' << 1 << ' ' << lr[v].fr << ' ' << w[v] << endl;
                }
                if (lr[v].sc < cnt - 1){
                    upd(lr[v].sc + 1, cnt, -w[v]);
//                    cout << v << ' ' << lr[v].sc + 2 << ' ' << cnt << ' ' << w[v] << endl;
                }
                w[v] = 0;
                v = p[v][0];
                del[v] = 1;
            }
            lc = v;
            v = a[it];
            while (!del[v]){
                del[v] = 1;
                upd(lr[v].fr, lr[v].sc + 1, -w[v]);
//                cout << v << ' ' << lr[v].fr + 1 << ' ' << lr[v].sc + 1 << ' ' << w[v] << endl;
                w[v] = 0;
                v = p[v][0];
            }
        }
    }
    for (int i = cnt; i <= n; i++)
        ans[i] = sum;
    for (int i = 1; i <= q; i++)
        cout << sum - ans[e[i]] << endl;
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5084 KB Output is correct
7 Correct 5 ms 5068 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 5 ms 5068 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 514 ms 76952 KB Output is correct
3 Correct 691 ms 90868 KB Output is correct
4 Correct 548 ms 75608 KB Output is correct
5 Correct 473 ms 76772 KB Output is correct
6 Correct 601 ms 80460 KB Output is correct
7 Correct 559 ms 77812 KB Output is correct
8 Correct 726 ms 93472 KB Output is correct
9 Correct 417 ms 81140 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 537 ms 77000 KB Output is correct
3 Correct 693 ms 93864 KB Output is correct
4 Correct 536 ms 75664 KB Output is correct
5 Correct 503 ms 76760 KB Output is correct
6 Correct 595 ms 80788 KB Output is correct
7 Correct 411 ms 80820 KB Output is correct
8 Correct 731 ms 88444 KB Output is correct
9 Correct 414 ms 81080 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5084 KB Output is correct
7 Correct 5 ms 5068 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 5 ms 5068 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 11 ms 5920 KB Output is correct
14 Correct 9 ms 5964 KB Output is correct
15 Correct 10 ms 5864 KB Output is correct
16 Correct 12 ms 5880 KB Output is correct
17 Correct 10 ms 5924 KB Output is correct
18 Correct 12 ms 5836 KB Output is correct
19 Correct 11 ms 5836 KB Output is correct
20 Correct 11 ms 5836 KB Output is correct
21 Correct 10 ms 5932 KB Output is correct
22 Correct 9 ms 5804 KB Output is correct
23 Correct 10 ms 5932 KB Output is correct
24 Correct 12 ms 5904 KB Output is correct
25 Correct 12 ms 5964 KB Output is correct
26 Correct 13 ms 5944 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 514 ms 76952 KB Output is correct
3 Correct 691 ms 90868 KB Output is correct
4 Correct 548 ms 75608 KB Output is correct
5 Correct 473 ms 76772 KB Output is correct
6 Correct 601 ms 80460 KB Output is correct
7 Correct 559 ms 77812 KB Output is correct
8 Correct 726 ms 93472 KB Output is correct
9 Correct 417 ms 81140 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 537 ms 77000 KB Output is correct
12 Correct 693 ms 93864 KB Output is correct
13 Correct 536 ms 75664 KB Output is correct
14 Correct 503 ms 76760 KB Output is correct
15 Correct 595 ms 80788 KB Output is correct
16 Correct 411 ms 80820 KB Output is correct
17 Correct 731 ms 88444 KB Output is correct
18 Correct 414 ms 81080 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 607 ms 78264 KB Output is correct
21 Correct 640 ms 94116 KB Output is correct
22 Correct 622 ms 78440 KB Output is correct
23 Correct 580 ms 77996 KB Output is correct
24 Correct 583 ms 76588 KB Output is correct
25 Correct 553 ms 77932 KB Output is correct
26 Correct 587 ms 76968 KB Output is correct
27 Correct 605 ms 78056 KB Output is correct
28 Correct 779 ms 80424 KB Output is correct
29 Correct 608 ms 77400 KB Output is correct
30 Correct 582 ms 78532 KB Output is correct
31 Correct 549 ms 80624 KB Output is correct
32 Correct 919 ms 89216 KB Output is correct
33 Correct 481 ms 82924 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5084 KB Output is correct
7 Correct 5 ms 5068 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 5 ms 5068 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 514 ms 76952 KB Output is correct
14 Correct 691 ms 90868 KB Output is correct
15 Correct 548 ms 75608 KB Output is correct
16 Correct 473 ms 76772 KB Output is correct
17 Correct 601 ms 80460 KB Output is correct
18 Correct 559 ms 77812 KB Output is correct
19 Correct 726 ms 93472 KB Output is correct
20 Correct 417 ms 81140 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 537 ms 77000 KB Output is correct
23 Correct 693 ms 93864 KB Output is correct
24 Correct 536 ms 75664 KB Output is correct
25 Correct 503 ms 76760 KB Output is correct
26 Correct 595 ms 80788 KB Output is correct
27 Correct 411 ms 80820 KB Output is correct
28 Correct 731 ms 88444 KB Output is correct
29 Correct 414 ms 81080 KB Output is correct
30 Correct 4 ms 4940 KB Output is correct
31 Correct 11 ms 5920 KB Output is correct
32 Correct 9 ms 5964 KB Output is correct
33 Correct 10 ms 5864 KB Output is correct
34 Correct 12 ms 5880 KB Output is correct
35 Correct 10 ms 5924 KB Output is correct
36 Correct 12 ms 5836 KB Output is correct
37 Correct 11 ms 5836 KB Output is correct
38 Correct 11 ms 5836 KB Output is correct
39 Correct 10 ms 5932 KB Output is correct
40 Correct 9 ms 5804 KB Output is correct
41 Correct 10 ms 5932 KB Output is correct
42 Correct 12 ms 5904 KB Output is correct
43 Correct 12 ms 5964 KB Output is correct
44 Correct 13 ms 5944 KB Output is correct
45 Correct 3 ms 4940 KB Output is correct
46 Correct 607 ms 78264 KB Output is correct
47 Correct 640 ms 94116 KB Output is correct
48 Correct 622 ms 78440 KB Output is correct
49 Correct 580 ms 77996 KB Output is correct
50 Correct 583 ms 76588 KB Output is correct
51 Correct 553 ms 77932 KB Output is correct
52 Correct 587 ms 76968 KB Output is correct
53 Correct 605 ms 78056 KB Output is correct
54 Correct 779 ms 80424 KB Output is correct
55 Correct 608 ms 77400 KB Output is correct
56 Correct 582 ms 78532 KB Output is correct
57 Correct 549 ms 80624 KB Output is correct
58 Correct 919 ms 89216 KB Output is correct
59 Correct 481 ms 82924 KB Output is correct
60 Correct 5 ms 4940 KB Output is correct
61 Correct 1082 ms 81372 KB Output is correct
62 Correct 1144 ms 92944 KB Output is correct
63 Correct 1123 ms 81360 KB Output is correct
64 Correct 1154 ms 81624 KB Output is correct
65 Correct 1146 ms 81436 KB Output is correct
66 Correct 1027 ms 89220 KB Output is correct
67 Correct 1073 ms 88004 KB Output is correct
68 Correct 1067 ms 89360 KB Output is correct
69 Correct 1104 ms 91372 KB Output is correct
70 Correct 1118 ms 88852 KB Output is correct
71 Correct 1065 ms 89452 KB Output is correct
72 Correct 1024 ms 92428 KB Output is correct
73 Correct 1135 ms 98244 KB Output is correct
74 Correct 952 ms 96424 KB Output is correct