Submission #921333

#TimeUsernameProblemLanguageResultExecution timeMemory
921333a_l_i_r_e_z_aDesignated Cities (JOI19_designated_cities)C++17
0 / 100
3 ms5224 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() #define len(x) ((int)(x).size()) const int maxn = 1e5 + 5; const int inf = 1e9 + 7; int n, q, dp[maxn]; vector<pair<int, pii>> adj[maxn]; void dfs1(int v, int p){ for(auto e: adj[v]){ if(e.F != p){ dp[1] += e.S.S; dfs1(e.F, v); } } } void dfs2(int v, int p){ for(auto e: adj[v]){ if(e.F != p){ dp[e.F] = dp[v] + e.S.F - e.S.S; dfs2(e.F, v); } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; int sm = 0; for(int i = 0; i < n - 1; i++){ int u, v, w1, w2; cin >> u >> v >> w1 >> w2; adj[u].pb(mp(v, mp(w1, w2))); adj[v].pb(mp(u, mp(w2, w1))); sm += w1 + w2; } dfs1(1, 0); dfs2(1, 0); int ans = 0; for(int i = 1; i <= n; i++) smax(ans, dp[i]); cin >> q; while(q--) cout << sm - ans << '\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...