//
// ROIGold.cpp
// Main calisma
//
// Created by Rakhman on 05/02/2019.
// Copyright © 2019 Rakhman. All rights reserved.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)
const int MXN = 2e5 + 1;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;
typedef long long llong;
typedef unsigned long long ullong;
using namespace std;
void istxt(bool yes){
if(yes == 1){
freopen("balancing.in", "r", stdin);
//freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/e.txt", "w", stdout);
}else{
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
}
}
int n, q, deq[MXN], res[MXN];
llong sum, ans, roads;
vector<pair<int, pair<int, int> > > g[MXN];
bool used[MXN];
void dfs(int v, int p){
for(int i = 0; i < g[v].size(); i++){
int to = g[v][i].F, cost = g[v][i].S.F;
if(to == p) {
roads += cost;
continue;
}
dfs(to, v);
}
}
void dfs2(int v, int p){
int cost;
for(int i = 0; i < g[v].size(); i++){
int to = g[v][i].F;
if(to == p){
cost = g[v][i].S.F;
continue;
}
}
roads -= cost;
ans = max(ans, roads);
for(int i = 0; i < g[v].size(); i++){
int to = g[v][i].F;
if(to == p){
continue;
}
roads += g[v][i].S.F;
dfs2(to, v);
roads -= g[v][i].S.F;
}
roads += cost;
}
int main () {
ios;
//istxt(0);
cin >> n;
for(int i = 1; i < n; i++){
int u, v, a, b;
cin >> u >> v >> a >> b;
g[u].pb({v, {a, b}});
g[v].pb({u, {b, a}});
deq[v] ++;
deq[u]++;
sum += a + b;
}
set<pair<llong, llong> > st;
for(int i = 1; i <= n; i++){
if(deq[i] == 1)
st.insert({g[i][0].S.S, i});
}
while(st.size() > 2){
int v = st.begin() -> S;
llong cost = st.begin() -> F;
used[v] = 1;
st.erase(st.begin());
int batya = -1;
for(int i = 0; i < g[v].size(); i++){
if(used[g[v][i].F] == 0){
batya = g[v][i].F;
break;
}
}
deq[batya]--;
if(deq[batya] == 1){
for(auto it : g[batya]){
if(used[it.F] == false){
st.insert({cost + it.S.S, it.F});
break;
}
}
continue;
}
res[st.size()] = res[st.size() + 1] + cost;
}
dfs(1, 0);
ans = roads;
dfs2(1, 0);
res[1] = sum - ans;
cin >> q;
while(q--){
int x;
cin >> x;
cout << res[x] << nl;
}
return 0;
}
Compilation message
designated_cities.cpp: In function 'void dfs(int, int)':
designated_cities.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs2(int, int)':
designated_cities.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
designated_cities.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:127:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void istxt(bool)':
designated_cities.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("balancing.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs2(int, int)':
designated_cities.cpp:87:11: warning: 'cost' may be used uninitialized in this function [-Wmaybe-uninitialized]
roads -= cost;
~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
4984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
409 ms |
19704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
423 ms |
19704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
4984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
409 ms |
19704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
4984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
