제출 #1327644

#제출 시각아이디문제언어결과실행 시간메모리
1327644spetrDesignated Cities (JOI19_designated_cities)C++20
7 / 100
431 ms56072 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;
vl ans;
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]);
        }
    }
}

ll dfs3(ll v, ll p){
    ll suma = 0;
    for(auto x : graf[v]){
        if (x[0] != p){
            suma = max(suma, dfs3(x[0], v) + x[1]);
        }
    }
    return suma;
}

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

    ll n;
    cin >> n;
    graf.resize(n);
    ans.resize(n+10, 0);

    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);

    ans[1] = optimum;
    vl cesty {0, 0};
    for (auto x : graf[root]){
        ll sub = dfs3(x[0], root) + x[1];
        cesty.push_back(sub);
    }
    sort(cesty.begin(), cesty.end()); reverse(cesty.begin(), cesty.end());
    ans[2] = optimum - (cesty[0] + cesty[1]);


    ll q;
    cin >>q;
    for (ll i = 0; i < q; i++){
        ll e;
        cin >> e;
        cout << ans[e] <<"\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...