oj.uz

Submission #261194

# Submission time Handle Problem Language Result Execution time Memory
261194 2020-08-11T14:00:48 Z keko37 Designated Cities (JOI19_designated_cities) C++14
7 / 100
 431 ms 47336 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;
llint a[MAXN], b[MAXN], c[MAXN], d[MAXN], e[MAXN];
vector <pair <int, pi> > v[MAXN];
llint sum[MAXN], mx[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];
        mx[x] = max(mx[x], to + mx[sus]);
    }
}

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

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] == 1) {
        dfs(1, 0);
        root(1, 0);
        cout << uk - jen;
    } else {
        return 0;
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5024 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 375 ms 33924 KB Output is correct
3 Correct 431 ms 46840 KB Output is correct
4 Correct 359 ms 32620 KB Output is correct
5 Correct 331 ms 33704 KB Output is correct
6 Correct 291 ms 35832 KB Output is correct
7 Correct 269 ms 32800 KB Output is correct
8 Correct 383 ms 47336 KB Output is correct
9 Correct 181 ms 30360 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5024 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 375 ms 33924 KB Output is correct
3 Correct 431 ms 46840 KB Output is correct
4 Correct 359 ms 32620 KB Output is correct
5 Correct 331 ms 33704 KB Output is correct
6 Correct 291 ms 35832 KB Output is correct
7 Correct 269 ms 32800 KB Output is correct
8 Correct 383 ms 47336 KB Output is correct
9 Correct 181 ms 30360 KB Output is correct
10 Incorrect 4 ms 5120 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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