oj.uz

Submission #384818

# Submission time Handle Problem Language Result Execution time Memory
384818 2021-04-02T11:01:06 Z kostia244 Designated Cities (JOI19_designated_cities) C++17
39 / 100
 415 ms 37228 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 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];
void find_pars(int v, int p) {
    for(auto [i, id] : g[v]) if(i != p) {
        par[i] = v;
        par_edge[i] = id^1;
        find_pars(i, v);
    }
}

void solve(int v) {
    for(int i = 0; i < 2*n; i++) used[i] = 0;
    find_pars(v, 0);
    sub_cost(v, 0);
    ll cur = sub[v];
    for(int i = 2; i <= n; i++) {
        auto [add, x] = find_leaf(v, 0);
        cur += add;
        greedy[i] = min(greedy[i], edgesum - cur);
        for(; x != v; x = par[x]) {
            used[par_edge[x]] = 1;
        }
    }
}

int 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);
    if(n <= 2000)
        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:99:19: warning: unused variable 'x' [-Wunused-variable]
   99 |     for(int f, t, x, y, i = 1; i < n; i++) {
      |                   ^
designated_cities.cpp:99:22: warning: unused variable 'y' [-Wunused-variable]
   99 |     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 5 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 5 ms 6764 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 5 ms 6636 KB Output is correct
8 Correct 5 ms 6636 KB Output is correct
9 Correct 6 ms 6636 KB Output is correct
10 Correct 7 ms 6636 KB Output is correct
11 Correct 5 ms 6636 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 323 ms 23276 KB Output is correct
3 Correct 410 ms 35088 KB Output is correct
4 Correct 334 ms 23276 KB Output is correct
5 Correct 351 ms 23396 KB Output is correct
6 Correct 354 ms 25068 KB Output is correct
7 Correct 265 ms 23436 KB Output is correct
8 Correct 415 ms 35564 KB Output is correct
9 Correct 189 ms 24028 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 327 ms 23276 KB Output is correct
3 Correct 390 ms 37228 KB Output is correct
4 Correct 394 ms 23404 KB Output is correct
5 Correct 327 ms 23476 KB Output is correct
6 Correct 345 ms 25352 KB Output is correct
7 Correct 205 ms 23820 KB Output is correct
8 Correct 365 ms 31168 KB Output is correct
9 Correct 180 ms 23772 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 5 ms 6764 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 5 ms 6636 KB Output is correct
8 Correct 5 ms 6636 KB Output is correct
9 Correct 6 ms 6636 KB Output is correct
10 Correct 7 ms 6636 KB Output is correct
11 Correct 5 ms 6636 KB Output is correct
12 Correct 7 ms 6636 KB Output is correct
13 Correct 87 ms 6892 KB Output is correct
14 Correct 109 ms 7148 KB Output is correct
15 Correct 86 ms 6892 KB Output is correct
16 Correct 102 ms 7020 KB Output is correct
17 Correct 84 ms 7020 KB Output is correct
18 Correct 86 ms 7020 KB Output is correct
19 Correct 84 ms 6892 KB Output is correct
20 Correct 82 ms 7020 KB Output is correct
21 Correct 86 ms 7020 KB Output is correct
22 Correct 86 ms 7020 KB Output is correct
23 Correct 76 ms 6984 KB Output is correct
24 Correct 48 ms 7020 KB Output is correct
25 Correct 106 ms 7260 KB Output is correct
26 Correct 39 ms 7020 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 323 ms 23276 KB Output is correct
3 Correct 410 ms 35088 KB Output is correct
4 Correct 334 ms 23276 KB Output is correct
5 Correct 351 ms 23396 KB Output is correct
6 Correct 354 ms 25068 KB Output is correct
7 Correct 265 ms 23436 KB Output is correct
8 Correct 415 ms 35564 KB Output is correct
9 Correct 189 ms 24028 KB Output is correct
10 Correct 5 ms 6636 KB Output is correct
11 Correct 327 ms 23276 KB Output is correct
12 Correct 390 ms 37228 KB Output is correct
13 Correct 394 ms 23404 KB Output is correct
14 Correct 327 ms 23476 KB Output is correct
15 Correct 345 ms 25352 KB Output is correct
16 Correct 205 ms 23820 KB Output is correct
17 Correct 365 ms 31168 KB Output is correct
18 Correct 180 ms 23772 KB Output is correct
19 Correct 5 ms 6636 KB Output is correct
20 Incorrect 340 ms 23404 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6636 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 5 ms 6764 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 5 ms 6636 KB Output is correct
8 Correct 5 ms 6636 KB Output is correct
9 Correct 6 ms 6636 KB Output is correct
10 Correct 7 ms 6636 KB Output is correct
11 Correct 5 ms 6636 KB Output is correct
12 Correct 5 ms 6636 KB Output is correct
13 Correct 323 ms 23276 KB Output is correct
14 Correct 410 ms 35088 KB Output is correct
15 Correct 334 ms 23276 KB Output is correct
16 Correct 351 ms 23396 KB Output is correct
17 Correct 354 ms 25068 KB Output is correct
18 Correct 265 ms 23436 KB Output is correct
19 Correct 415 ms 35564 KB Output is correct
20 Correct 189 ms 24028 KB Output is correct
21 Correct 5 ms 6636 KB Output is correct
22 Correct 327 ms 23276 KB Output is correct
23 Correct 390 ms 37228 KB Output is correct
24 Correct 394 ms 23404 KB Output is correct
25 Correct 327 ms 23476 KB Output is correct
26 Correct 345 ms 25352 KB Output is correct
27 Correct 205 ms 23820 KB Output is correct
28 Correct 365 ms 31168 KB Output is correct
29 Correct 180 ms 23772 KB Output is correct
30 Correct 7 ms 6636 KB Output is correct
31 Correct 87 ms 6892 KB Output is correct
32 Correct 109 ms 7148 KB Output is correct
33 Correct 86 ms 6892 KB Output is correct
34 Correct 102 ms 7020 KB Output is correct
35 Correct 84 ms 7020 KB Output is correct
36 Correct 86 ms 7020 KB Output is correct
37 Correct 84 ms 6892 KB Output is correct
38 Correct 82 ms 7020 KB Output is correct
39 Correct 86 ms 7020 KB Output is correct
40 Correct 86 ms 7020 KB Output is correct
41 Correct 76 ms 6984 KB Output is correct
42 Correct 48 ms 7020 KB Output is correct
43 Correct 106 ms 7260 KB Output is correct
44 Correct 39 ms 7020 KB Output is correct
45 Correct 5 ms 6636 KB Output is correct
46 Incorrect 340 ms 23404 KB Output isn't correct
47 Halted 0 ms 0 KB -