제출 #723412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723412		doowey	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	376 ms	60544 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;

struct E{
    int nx;
    int C;
    int D;
};

vector<E> T[N];

ll sol[N];

ll cum;
ll W[N];
pii mx[N];

void dfs0(int u, int pa){
    mx[u] = mp(0ll, u);
    for(auto x : T[u]){
        if(x.nx == pa) continue;
        cum += x.D;
        W[x.nx] = W[u] + x.C - x.D;
        dfs0(x.nx, u);
        mx[u] = max(mx[u], mp(mx[x.nx].fi + x.C, mx[x.nx].se));
    }
}

ll take = 0ll;

ll maxi = 0ll;
int ud;
int vd;

void dfs1(int u, int pa){
    pii r1, r2;
    r1 = r2 = mp(0ll, u);
    pii G;
    for(auto x : T[u]){
        if(x.nx == pa) continue;
        dfs1(x.nx, u);
        G = mx[x.nx];
        G.fi += x.C;
        if(G > r1){
            r2 = r1;
            r1 = G;
        }
        else if(G > r2){
            r2 = G;
        }
    }
    if(cum + W[u] + r1.fi + r2.fi > maxi){
        maxi = cum + W[u] + r1.fi + r2.fi;
        ud = r1.se;
        vd = r2.se;
    }
}

vector<ll> wei[N];

void dfs2(int node, int par){
    wei[node].push_back(0ll);
    for(auto x : T[node]){
        if(x.nx == par) continue;
        dfs2(x.nx, node);
        wei[x.nx].back() += x.C;
        cum += x.D;
        if(wei[node].size() < wei[x.nx].size()) swap(wei[node], wei[x.nx]);
        if(wei[node].back() > wei[x.nx].back()) swap(wei[node].back(), wei[x.nx].back());
        for(auto y : wei[x.nx]) {
            wei[node].push_back(y);
        }
        wei[x.nx].clear();
    }
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    int ui, vi, ci, di;
    for(int i = 1; i < n; i ++ ){
        cin >> ui >> vi >> ci >> di;
        T[ui].push_back({vi, ci, di});
        T[vi].push_back({ui, di, ci});
        take += ci + di;
    }
    cum = 0ll;
    dfs0(1, -1);
    for(int i = 1; i <= n; i ++ ){
        sol[1] = max(sol[1], W[i] + cum);
    }
    dfs1(1, -1);
    cum = 0ll;
    dfs2(ud, -1);
    sort(wei[ud].begin(), wei[ud].end());
    reverse(wei[ud].begin(), wei[ud].end());
    for(int ln = 0; ln < n - 1; ln ++ ){
        cum += wei[ud][ln];
        sol[ln + 2] = max(sol[ln + 2], cum);
    }
    int q;
    cin >> q;
    int r;
    for(int ii = 1; ii <= q; ii ++ ){
        cin >> r;
        cout << take - sol[r] << "\n";
    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44