Submission #426921

#	Time	Username	Problem	Language	Result	Execution time	Memory
426921		Hideo	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	2086 ms	43316 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[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], lg[2][N];
    int rv[N], del[N], cnt;
    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, 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);
                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];
    }
     
    void build (int v, int l, int r){
        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];
        }
    }
     
    //void upd(int l, int r, int val){
    //    for (l += n, r += n; l < r; l >>= 1, r >>= 1){
    //        if (l & 1)
    //            t[l++].fr += value;
    //        if (r & 1)
    //            t[--r].fr += value;
    //    }
    //}
     
    int hg;
     
    void apply(int p, int value) {
      t[p].fr += value;
      if (p < cnt) lz[p] += value;
    }
     
    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 build2(int p) {
      while (p > 1) p >>= 1, t[p] = (t[p<<1].fr > t[p<<1|1].fr ? t[p<<1] : t[p<<1|1]), t[p].fr += lz[p];
    }
     
    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);
      }
      build2(l0);
      build2(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 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;
     
    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);
        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]);
        }
        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 = 1; i < cnt; i++){
            t[cnt + i].sc = i;
            upd(i, i + 1, dis(lc, a[i]));
        }
        //build(1, 1, cnt);
        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(1, cnt);
            int it = temp.sc, val = temp.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(lr[v].fr, lr[v].sc + 1, -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, lr[v].fr, -w[v]);
                    if (lr[v].sc < cnt)
                        upd(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(lr[v].fr, lr[v].sc + 1, -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:212:5: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  212 |     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