제출 #261194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261194		keko37	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	431 ms	47336 KiB

designated_cities

#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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44