Submission #223875

#TimeUsernameProblemLanguageResultExecution timeMemory
223875osaaateiasavtnlDesignated Cities (JOI19_designated_cities)C++14
7 / 100
353 ms34040 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcount #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int N = 2e5 + 7; vector <ii> g[N]; int sum[N]; void dfs1(int u, int p) { for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p) { dfs1(v, u); sum[u] += sum[v] + c; } } } const int INF = 1e18; int ans = INF; void dfs2(int u, int p, int up) { for (auto e : g[u]) { int v = e.f, c = e.s; if (v == p) { up += c; } } ans = min(ans, up + sum[u]); for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p) { dfs2(v, u, up + sum[u] - sum[v] - c); } } } signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int u, v, a, b; cin >> u >> v >> a >> b; g[u].app(mp(v, a)); g[v].app(mp(u, b)); } dfs1(1, 1); dfs2(1, 1, 0); cout << ans << endl; }
#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...