Submission #132761

#TimeUsernameProblemLanguageResultExecution timeMemory
132761youngyojunDesignated Cities (JOI19_designated_cities)C++11
7 / 100
358 ms34272 KiB
#include <bits/stdc++.h> #define eb emplace_back using namespace std; typedef long long ll; const int MAXN = 200055; vector<int> G[MAXN]; int prt[MAXN], dep[MAXN], cnt[MAXN], dfo[MAXN]; int A[MAXN], B[MAXN], C[MAXN], D[MAXN]; ll Ans[MAXN], Sum; int N, Q; void predfs(int i, int &c) { cnt[i] = 1; dfo[i] = ++c; for(int e : G[i]) { int v = A[e]^B[e]^i; if(v == prt[i]) continue; dep[v] = dep[i] + 1; prt[v] = i; predfs(v, c); cnt[i] += cnt[v]; } } void dfsOne(int i, ll sum) { if(Ans[1] < sum) Ans[1] = sum; for(int e : G[i]) if(A[e] != prt[i]) dfsOne(B[e], sum - D[e] + C[e]); } void getAnsOne() { { int c = 0; predfs(1, c); } for(int i = 1; i < N; i++) if(prt[A[i]] == B[i]) { swap(A[i], B[i]); swap(C[i], D[i]); } ll sum = 0; for(int i = 1; i < N; i++) sum += D[i]; dfsOne(1, sum); } int main() { ios::sync_with_stdio(false); cin >> N; for(int i = 1; i < N; i++) { cin >> A[i] >> B[i] >> C[i] >> D[i]; G[A[i]].eb(i); G[B[i]].eb(i); Sum += C[i] + D[i]; } getAnsOne(); cin >> Q; for(int a; Q--;) { cin >> a; printf("%lld\n", Sum - Ans[a]); } 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...