oj.uz

Submission #384834

# Submission time Handle Problem Language Result Execution time Memory
384834 2021-04-02T11:30:53 Z kostia244 Designated Cities (JOI19_designated_cities) C++17
100 / 100
 757 ms 87816 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int maxn = 4e5 + 12;
int n, cst[2*maxn];
ll edgesum = 0;
vector<array<int, 2>> g[maxn];


ll sub[maxn];
void sub_cost(int v, int p) {
    sub[v] = 0;
    for(auto [i, id] : g[v]) if(i != p) {
        sub_cost(i, v);
        sub[v] += sub[i] + cst[id];
    }
}
ll arb[maxn];
void reroot_cost(int v, int p, ll sum) {
    arb[v] = sum;
    for(auto [i, id] : g[v]) if(i!=p) {
        reroot_cost(i, v, sum-cst[id]+cst[id^1]);
    }
}
ll greedy[maxn], used[maxn];
array<ll, 2> find_leaf(int v, int p) {
    array<ll, 2> ans = {0, v};
    for(auto [i, id] : g[v]) if(i != p) {
        auto t = find_leaf(i, v);
        //cout << t[0]+( cst[id^1]*!used[id^1]) << endl;
        t[0] += cst[id^1]*!used[id^1];
        ans = max(ans, t);
    }
    return ans;
}

array<ll, 2> far[maxn];
void sub_far(int v, int p) {
    far[v] = {0, -(1ll<<56)};
    for(auto &[i, id] : g[v]) if(i != p) {
        sub_far(i, v);
        auto t = far[i];
        t[0] += cst[id^1];
        t[1] += cst[id^1];
        if(far[v][0] < t[0])
            swap(far[v][0], t[0]);
        far[v][1] = max(far[v][1], t[0]);
    }
}
ll F[maxn];
void reroot_far(int v, int p, ll over) {
    F[v] = max(far[v][0], over);
    //cout << v << " -- " << F[v] << endl;
    for(auto [i, id] : g[v]) if(i != p) {
        reroot_far(i, v, cst[id]+max(over, far[i][0]+cst[id^1] == far[v][0] ? far[v][1] : far[v][0]));
    }
}
ll solFor2 = 0;
int solve2() {
    sub_far(1, 0);
    reroot_far(1, 0, -(1ll<<60));
    array<ll, 2> sol = {-(1ll<<60), -1};
    for(int i = 1; i <= n; i++)
        sol = max(sol, {F[i]+arb[i], i});
    //cout << edgesum << " ? " << sol[0] << " " << sol[1] << endl;
    //cout << arb[3] << " " << arb[4] << endl;
    //cout << sol[0] << "/ " << edgesum << endl;
    solFor2 = edgesum - sol[0];
    return sol[1];
}

int par[maxn], par_edge[maxn], tin[maxn], tout[maxn], timer = 1;
int tinToV[maxn];
vector<ll> dep;
void find_pars(int v, int p, ll d) {
    tin[v] = timer++;
    dep[tin[v]] = d;
    tinToV[tin[v]] = v;
    for(auto [i, id] : g[v]) if(i != p) {
        par[i] = v;
        par_edge[i] = id^1;
        find_pars(i, v, d + cst[id^1]);
    }
    tout[v] = timer-1;
}

struct SegTree {
    struct Node {
        array<ll, 2> val;
        ll lazy;
        Node(ll x = 0) : val{x, 0}, lazy(0) {}
        Node(array<ll, 2> x) : val{x[0], x[1]}, lazy(0) {}
        void apply(ll x) {
            lazy += x;
            val[0] += x;
        }
        void push(Node &l, Node &r) {
            l.apply(lazy), r.apply(lazy);
            lazy = 0;
        }
        friend Node operator+(const Node &a, const Node &b) {
            return Node(max(a.val, b.val));
        }
    };
    int n;
    vector<Node> tree;
    SegTree(int n) : n(n), tree(4*n) {}
    void build(int v, int l, int r, vector<ll> &dep) {
        if(l == r) {
            tree[v].val = {dep[l], l};
            return;
        }
        int mid = (l+r)/2;
        build(2*v, l, mid, dep);
        build(2*v+1, mid+1, r, dep);
        tree[v] = tree[2*v]+tree[2*v+1];
    }
    void build(vector<ll> &dep) {
        build(1, 1, n, dep);
    }
    void update(int v, int l, int r, int ql, int qr, ll add) {
        if(r < ql || qr < l) return;
        if(ql <= l && r <= qr) {
            tree[v].apply(add);
            return;
        }
        int mid = (l+r)/2;
        tree[v].push(tree[2*v], tree[2*v+1]);
        update(2*v, l, mid, ql, qr, add);
        update(2*v+1, mid+1, r, ql, qr, add);
        tree[v] = tree[2*v]+tree[2*v+1];
    }
    void update(int ql, int qr, ll add) {
        update(1, 1, n, ql, qr, add);
    }
    Node query(int v, int l, int r, int ql, int qr) {
        if(r < ql || qr < l) return Node();
        if(ql <= l && r <= qr) return tree[v];
        int mid = (l+r)/2;
        tree[v].push(tree[2*v], tree[2*v+1]);
        return query(2*v, l, mid, ql, qr) + query(2*v+1, mid+1, r, ql, qr);
    }
    array<ll, 2> query(int ql, int qr) {
        return query(1, 1, n, ql, qr).val;
    }
};

void solve(int v) {
    for(int i = 0; i < 2*n; i++) used[i] = 0;
    dep.resize(n+1);
    find_pars(v, 0, 0);
    sub_cost(v, 0);
    ll cur = sub[v];
    SegTree st(n);
    st.build(dep);
    //for(int i = 1; i <= n; i++)
    //    cout << st.query(tin[i], tin[i])[0] << " vs " << dep[i] << endl;
    //cout << '\n';
    for(int i = 2; i <= n; i++) {
        auto [add, x] = st.query(1, n);
        cur += add;
        x = tinToV[x];
        greedy[i] = edgesum - cur;
        for(; x != v && !used[par_edge[x]]; x = par[x]) {
            st.update(tin[x], tout[x], -cst[par_edge[x]]);
            used[par_edge[x]] = 1;
        }
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int f, t, x, y, i = 1; i < n; i++) {
        cin >> f >> t >> cst[2*i-1] >> cst[2*i-2];
        edgesum += cst[2*i-1];
        edgesum += cst[2*i-2];
        g[f].push_back({t, 2*i-2});
        g[t].push_back({f, 2*i-1});
    }
    sub_cost(1, 0);
    reroot_cost(1, 0, sub[1]);
    //for(int i = 1; i <= n; i++) cout << arb[i] << " "; cout << endl;
    auto point = solve2();

    memset(greedy, 0x4f, sizeof greedy);
    solve(point);

    int q;
    cin >> q;
    greedy[1] = edgesum-*max_element(arb+1, arb+n+1);
    //greedy[2] = solFor2;
    for(int t; q--;) {
        cin >> t;
        cout << greedy[t] << '\n';
    }
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:175:19: warning: unused variable 'x' [-Wunused-variable]
  175 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                   ^
designated_cities.cpp:175:22: warning: unused variable 'y' [-Wunused-variable]
  175 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                      ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 9 ms 12908 KB Output is correct
7 Correct 10 ms 12908 KB Output is correct
8 Correct 9 ms 12908 KB Output is correct
9 Correct 9 ms 12908 KB Output is correct
10 Correct 9 ms 12908 KB Output is correct
11 Correct 9 ms 12928 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 694 ms 65472 KB Output is correct
3 Correct 645 ms 81388 KB Output is correct
4 Correct 630 ms 65644 KB Output is correct
5 Correct 637 ms 65456 KB Output is correct
6 Correct 676 ms 67628 KB Output is correct
7 Correct 547 ms 65008 KB Output is correct
8 Correct 733 ms 80620 KB Output is correct
9 Correct 451 ms 64852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 650 ms 65644 KB Output is correct
3 Correct 639 ms 81308 KB Output is correct
4 Correct 619 ms 65644 KB Output is correct
5 Correct 626 ms 65632 KB Output is correct
6 Correct 691 ms 68244 KB Output is correct
7 Correct 461 ms 64724 KB Output is correct
8 Correct 716 ms 75884 KB Output is correct
9 Correct 507 ms 64724 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 9 ms 12908 KB Output is correct
7 Correct 10 ms 12908 KB Output is correct
8 Correct 9 ms 12908 KB Output is correct
9 Correct 9 ms 12908 KB Output is correct
10 Correct 9 ms 12908 KB Output is correct
11 Correct 9 ms 12928 KB Output is correct
12 Correct 9 ms 12908 KB Output is correct
13 Correct 13 ms 13420 KB Output is correct
14 Correct 12 ms 13676 KB Output is correct
15 Correct 12 ms 13420 KB Output is correct
16 Correct 12 ms 13420 KB Output is correct
17 Correct 12 ms 13420 KB Output is correct
18 Correct 12 ms 13420 KB Output is correct
19 Correct 12 ms 13420 KB Output is correct
20 Correct 12 ms 13420 KB Output is correct
21 Correct 12 ms 13548 KB Output is correct
22 Correct 12 ms 13420 KB Output is correct
23 Correct 13 ms 13420 KB Output is correct
24 Correct 12 ms 13420 KB Output is correct
25 Correct 14 ms 13676 KB Output is correct
26 Correct 12 ms 13420 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 694 ms 65472 KB Output is correct
3 Correct 645 ms 81388 KB Output is correct
4 Correct 630 ms 65644 KB Output is correct
5 Correct 637 ms 65456 KB Output is correct
6 Correct 676 ms 67628 KB Output is correct
7 Correct 547 ms 65008 KB Output is correct
8 Correct 733 ms 80620 KB Output is correct
9 Correct 451 ms 64852 KB Output is correct
10 Correct 9 ms 12908 KB Output is correct
11 Correct 650 ms 65644 KB Output is correct
12 Correct 639 ms 81308 KB Output is correct
13 Correct 619 ms 65644 KB Output is correct
14 Correct 626 ms 65632 KB Output is correct
15 Correct 691 ms 68244 KB Output is correct
16 Correct 461 ms 64724 KB Output is correct
17 Correct 716 ms 75884 KB Output is correct
18 Correct 507 ms 64724 KB Output is correct
19 Correct 16 ms 12908 KB Output is correct
20 Correct 654 ms 65388 KB Output is correct
21 Correct 668 ms 87816 KB Output is correct
22 Correct 670 ms 70508 KB Output is correct
23 Correct 663 ms 72300 KB Output is correct
24 Correct 663 ms 71276 KB Output is correct
25 Correct 658 ms 72236 KB Output is correct
26 Correct 633 ms 70884 KB Output is correct
27 Correct 654 ms 71780 KB Output is correct
28 Correct 724 ms 74300 KB Output is correct
29 Correct 693 ms 72556 KB Output is correct
30 Correct 657 ms 70752 KB Output is correct
31 Correct 556 ms 71260 KB Output is correct
32 Correct 710 ms 82540 KB Output is correct
33 Correct 458 ms 71068 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 9 ms 12908 KB Output is correct
7 Correct 10 ms 12908 KB Output is correct
8 Correct 9 ms 12908 KB Output is correct
9 Correct 9 ms 12908 KB Output is correct
10 Correct 9 ms 12908 KB Output is correct
11 Correct 9 ms 12928 KB Output is correct
12 Correct 9 ms 12908 KB Output is correct
13 Correct 694 ms 65472 KB Output is correct
14 Correct 645 ms 81388 KB Output is correct
15 Correct 630 ms 65644 KB Output is correct
16 Correct 637 ms 65456 KB Output is correct
17 Correct 676 ms 67628 KB Output is correct
18 Correct 547 ms 65008 KB Output is correct
19 Correct 733 ms 80620 KB Output is correct
20 Correct 451 ms 64852 KB Output is correct
21 Correct 9 ms 12908 KB Output is correct
22 Correct 650 ms 65644 KB Output is correct
23 Correct 639 ms 81308 KB Output is correct
24 Correct 619 ms 65644 KB Output is correct
25 Correct 626 ms 65632 KB Output is correct
26 Correct 691 ms 68244 KB Output is correct
27 Correct 461 ms 64724 KB Output is correct
28 Correct 716 ms 75884 KB Output is correct
29 Correct 507 ms 64724 KB Output is correct
30 Correct 9 ms 12908 KB Output is correct
31 Correct 13 ms 13420 KB Output is correct
32 Correct 12 ms 13676 KB Output is correct
33 Correct 12 ms 13420 KB Output is correct
34 Correct 12 ms 13420 KB Output is correct
35 Correct 12 ms 13420 KB Output is correct
36 Correct 12 ms 13420 KB Output is correct
37 Correct 12 ms 13420 KB Output is correct
38 Correct 12 ms 13420 KB Output is correct
39 Correct 12 ms 13548 KB Output is correct
40 Correct 12 ms 13420 KB Output is correct
41 Correct 13 ms 13420 KB Output is correct
42 Correct 12 ms 13420 KB Output is correct
43 Correct 14 ms 13676 KB Output is correct
44 Correct 12 ms 13420 KB Output is correct
45 Correct 16 ms 12908 KB Output is correct
46 Correct 654 ms 65388 KB Output is correct
47 Correct 668 ms 87816 KB Output is correct
48 Correct 670 ms 70508 KB Output is correct
49 Correct 663 ms 72300 KB Output is correct
50 Correct 663 ms 71276 KB Output is correct
51 Correct 658 ms 72236 KB Output is correct
52 Correct 633 ms 70884 KB Output is correct
53 Correct 654 ms 71780 KB Output is correct
54 Correct 724 ms 74300 KB Output is correct
55 Correct 693 ms 72556 KB Output is correct
56 Correct 657 ms 70752 KB Output is correct
57 Correct 556 ms 71260 KB Output is correct
58 Correct 710 ms 82540 KB Output is correct
59 Correct 458 ms 71068 KB Output is correct
60 Correct 9 ms 12908 KB Output is correct
61 Correct 688 ms 72032 KB Output is correct
62 Correct 700 ms 87788 KB Output is correct
63 Correct 627 ms 70864 KB Output is correct
64 Correct 696 ms 72428 KB Output is correct
65 Correct 660 ms 71212 KB Output is correct
66 Correct 676 ms 72428 KB Output is correct
67 Correct 673 ms 71140 KB Output is correct
68 Correct 671 ms 72060 KB Output is correct
69 Correct 755 ms 74348 KB Output is correct
70 Correct 678 ms 72684 KB Output is correct
71 Correct 622 ms 70880 KB Output is correct
72 Correct 584 ms 71388 KB Output is correct
73 Correct 757 ms 82540 KB Output is correct
74 Correct 491 ms 71380 KB Output is correct