제출 #261200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261200		keko37	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	445 ms	49788 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, 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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44