Submission #1007363

#TimeUsernameProblemLanguageResultExecution timeMemory
1007363AdamGSDesignated Cities (JOI19_designated_cities)C++17
7 / 100
115 ms33876 KiB
#include<bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e5+7; vector<pair<ll,ll>>V[LIM]; ll wynik[LIM], sum; void DFS(int x, int o) { for(auto i : V[x]) if(i.st==o) sum+=i.nd; else DFS(i.st, x); } void DFS2(int x, int o) { for(auto i : V[x]) if(i.st==o) sum-=i.nd; wynik[1]=max(wynik[1], sum); for(auto i : V[x]) if(i.st!=o) { sum+=i.nd; DFS2(i.st, x); sum-=i.nd; } for(auto i : V[x]) if(i.st==o) sum+=i.nd; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; ll summ=0; rep(i, n-1) { ll a, b, c, d; cin >> a >> b >> c >> d; --a; --b; V[a].pb({b, c}); V[b].pb({a, d}); summ+=c+d; } DFS(0, 0); DFS2(0, 0); rep(i, n+1) wynik[i]=summ-wynik[i]; int q; cin >> q; while(q--) { int x; cin >> x; cout << wynik[x] << '\n'; } }
#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...