Submission #1327679

#TimeUsernameProblemLanguageResultExecution timeMemory
1327679spetrDesignated Cities (JOI19_designated_cities)C++20
16 / 100
426 ms65936 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;
vector<pl> maximum;
vl cost; 
ll ans2 = 2e18; 

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){
    cost[v] = 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 best1 = 0;
    ll best2 = 0;
    
    for(auto x : graf[v]){
        if (x[0] != p){
            ll down = dfs3(x[0], v) + x[1]; 
            
            if (down > best1) {
                best2 = best1;
                best1 = down;
            } else if (down > best2) {
                best2 = down;
            }
        }
    }
    ll candidate = cost[v] - best1 - best2;
    if (candidate < ans2) {
        ans2 = candidate;
    }
    
    return best1;
}

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

    ll n;
    cin >> n;
    graf.resize(n);
    ans.resize(n+10, 0);
    cost.resize(n, 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);

    maximum.resize(n, {0,0});
    ans[1] = optimum;

    dfs3(0, -1);
    ans[2] = ans2;

    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...