제출 #1327637

#제출 시각아이디문제언어결과실행 시간메모리
1327637spetrDesignated Cities (JOI19_designated_cities)C++20
7 / 100
193 ms53720 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

vector<vector<vl>> graf;
ll s = 0;
ll optimum = 2e18;
ll root = 0;

void dfs1(ll v, ll p){
    for(auto x : graf[v]){
        if (x[0] != p){
            s += x[1];
            dfs1(x[0], v);
        }
    }
}

void dfs2(ll v, ll p, ll sub){
    if (sub < optimum){
        optimum = sub;
        root = v;
    }
    for(auto x : graf[v]){
        if (x[0] != p){
            dfs2(x[0], v, sub - x[1] + x[2]);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    graf.resize(n);

    for (ll i = 0; i < n-1; i++){
        ll a,b,c,d;
        cin >>a >>b  >>c >>d;
        a--; b--;
        graf[a].push_back({b,c, d});
        graf[b].push_back({a,d, c});
    }

    dfs1(0, -1);
    dfs2(0, -1, s);

    ll q;
    cin >>q;
    for (ll i = 0; i < q; i++){
        ll e;
        cin >> e;
        cout << optimum <<"\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...