Submission #1091264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091264		pokmui9909	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	129 ms	40272 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

struct Edge{
    ll v, a, b;
};
vector<Edge> T[200005], C[200005];
ll N, Q, Ans[200005], Val[200005];

void cal1(ll u, ll p){
    for(auto e : T[u]){
        if(e.v == p) continue;
        Val[1] += e.a;
        cal1(e.v, u);
    }
}
void cal2(ll u, ll p){
    for(auto e : T[u]){
        if(e.v == p) continue;
        Val[e.v] = Val[u] - e.a + e.b;
        cal2(e.v, u);
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N;
    for(ll i = 1; i < N; i++){
        ll u, v, a, b; cin >> u >> v >> a >> b;
        T[u].push_back({v, a, b}); T[v].push_back({u, b, a});
    }
    cal1(1, -1); cal2(1, -1);
    Ans[1] = *min_element(Val + 1, Val + N + 1);
    cin >> Q;
    while(Q--){
        ll t; cin >> t;
        cout << Ans[t] << '\n';
    }
}

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