oj.uz

Submission #261200

# Submission time Handle Problem Language Result Execution time Memory
261200 2020-08-11T14:14:41 Z keko37 Designated Cities (JOI19_designated_cities) C++14
7 / 100
 445 ms 49788 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 200005;

llint n, q, uk, jen, dva;
llint a[MAXN], b[MAXN], c[MAXN], d[MAXN], e[MAXN];
vector <pair <int, pi> > v[MAXN];
llint sum[MAXN], mx[MAXN], dr[MAXN], ind_mx[MAXN], ind_dr[MAXN], gore[MAXN], to_rod[MAXN];

void dfs (int x, int rod) {
    for (auto par : v[x]) {
        int sus = par.first;
        if (sus == rod) continue;
        llint to = par.second.first;
        llint from = par.second.second;
        dfs(sus, x);
        sum[x] += from + sum[sus];

        llint val = to + mx[sus];
        if (val > dr[x]) {
            dr[x] = val; ind_dr[x] = sus;
        }
        if (dr[x] > mx[x]) {
            swap(mx[x], dr[x]);
            swap(ind_mx[x], ind_dr[x]);
        }
    }
}

void root (int x, int rod) {
    jen = max(jen, sum[x]);
    for (auto par : v[x]) {
        int sus = par.first;
        llint to = par.second.first;
        llint from = par.second.second;
        if (sus == rod) {
            gore[x] = to + gore[rod];
            if (x != ind_mx[rod]) {
                gore[x] = max(gore[x], to + mx[rod]);
            } else {
                gore[x] = max(gore[x], to + dr[rod]);
            }
            continue;
        }

        sum[x] -= from + sum[sus];
        sum[sus] += to + sum[x];
        root(sus, x);
        sum[sus] -= to + sum[x];
        sum[x] += from + sum[sus];
    }
    dva = max(dva, sum[x] + mx[x]);
    dva = max(dva, sum[x] + gore[x]);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        v[a[i]].push_back({b[i], {c[i], d[i]}});
        v[b[i]].push_back({a[i], {d[i], c[i]}});
        uk += c[i] + d[i];
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> e[i];
    }
    if (q == 1 && e[0] <= 2) {
        dfs(1, 0);
        root(1, 0);
        if (e[0] == 1) cout << uk - jen; else cout << uk - dva;
    } else {
        return 0;
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 368 ms 33788 KB Output is correct
3 Correct 442 ms 49144 KB Output is correct
4 Correct 377 ms 33720 KB Output is correct
5 Correct 384 ms 33580 KB Output is correct
6 Correct 405 ms 36088 KB Output is correct
7 Correct 329 ms 32548 KB Output is correct
8 Correct 445 ms 49788 KB Output is correct
9 Correct 221 ms 25500 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Incorrect 418 ms 40148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 368 ms 33788 KB Output is correct
3 Correct 442 ms 49144 KB Output is correct
4 Correct 377 ms 33720 KB Output is correct
5 Correct 384 ms 33580 KB Output is correct
6 Correct 405 ms 36088 KB Output is correct
7 Correct 329 ms 32548 KB Output is correct
8 Correct 445 ms 49788 KB Output is correct
9 Correct 221 ms 25500 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Incorrect 418 ms 40148 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -