Submission #427015

#	Time	Username	Problem	Language	Result	Execution time	Memory
427015		Hideo	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	2072 ms	45568 KiB

designated_cities

//#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 ll 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 apply(int p, int value) {
  t[p].fr += value;
  if (p < cnt) lz[p] += value;
}

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) {
      apply(i<<1, lz[i]);
      apply(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) apply(l++, value);
    if (r&1) apply(--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});
            }
        }
    }
}

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];
    }
    for (int i = 3; i <= cnt; i++){
        pi temp = query(0, cnt);
        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 nw = lca(lc, a[it]);
            int v = lc;
            while (v != nw){
                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;
            }
            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 + 1; i <= n; i++)
        ans[i] = sum;
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        int e;
        cin >> e;
        cout << sum - ans[e] << endl;
    }
}

Compilation message (stderr)

designated_cities.cpp:175:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  175 | 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