This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
template<typename T>
bool minimize(T& a, const T& b){
if(a > b){
return a = b, true;
}
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
return a = b, true;
}
return false;
}
using ll = long long;
using ld = long double;
using ull = unsigned long long;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif // LOCAL
int N;
cin >> N;
vector<vector<tuple<int, int, int>>> adj(N);
for(int i = 0; i < N - 1; ++i){
int u, v, c, d;
cin >> u >> v >> c >> d;
--u, --v;
adj[u].emplace_back(v, c, d);
adj[v].emplace_back(u, d, c);
}
vector<ll> f(N), g(N);
function<void(int, int)> dfs = [&](int u, int p){
for(auto [v, c, d] : adj[u]) if(v != p){
dfs(v, u);
f[u] += f[v] + c;
}
};
dfs(0, -1);
g[0] = f[0];
function<void(int, int)> reroot_dfs = [&](int u, int p){
for(auto [v, c, d] : adj[u]) if(v != p){
g[v] = g[u] - c + d;
reroot_dfs(v, u);
}
};
reroot_dfs(0, -1);
vector<long long> answer(N + 1, LLONG_MAX);
for(int i = 0; i < N; ++i){
answer[1] = min(answer[1], g[i]);
}
int Q;
cin >> Q;
while(Q--){
int k;
cin >> k;
cout << answer[k] << '\n';
}
return 0;
}
Compilation message (stderr)
designated_cities.cpp: In lambda function:
designated_cities.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for(auto [v, c, d] : adj[u]) if(v != p){
| ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for(auto [v, c, d] : adj[u]) if(v != p){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |