//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 2e5;
vector<pair<int, int> > adj[N + 1];
int n, q, w[2 * N];
long long sum_all;
void read()
{
cin >> n;
for (int i = 1; i < n; ++ i)
{
int u, v, c, d;
cin >> u >> v >> c >> d;
adj[u].emplace_back(v, i * 2);
adj[v].emplace_back(u, i * 2 + 1);
w[2 * i] = c;
w[2 * i + 1] = d;
sum_all += c;
sum_all += d;
}
cin >> q;
}
long long res[N + 1];
bool used[32];
bool DFS_brute(int u, int p)
{
for (auto [v, i] : adj[u])
{
if (v == p)
{
continue;
}
used[i ^ 1] = true;
DFS_brute(v, u);
}
}
void sub1()
{
memset(res, 0x3f, sizeof(res));
for (int mask = 0; mask < (1 << n); ++ mask)
{
memset(used, 0, sizeof(used));
for (int u = 1; u <= n; ++ u)
{
if ((mask >> (u - 1)) & 1)
{
DFS_brute(u, 0);
}
}
long long sum = 0;
for (int i = 0; i < 2 * n; ++ i)
{
if (!used[i])
{
sum += w[i];
}
}
res[__builtin_popcount(mask)] = min(res[__builtin_popcount(mask)], sum);
}
while(q--)
{
int x;
cin >> x;
cout << res[x] << '\n';
}
}
multiset<long long> f, trash;
long long dp_dw[N + 1], dp_up[N + 1], sum;
void DFS_dw(int u, int p)
{
for (auto [v, i] : adj[u])
{
if (v == p)
{
continue;
}
DFS_dw(v, u);
sum += w[i ^ 1];
dp_dw[u] = max(dp_dw[u], dp_dw[v] + w[i]);
}
bool flag = true;
for (auto [v, i] : adj[u])
{
if (v == p)
{
continue;
}
if (flag && dp_dw[u] == dp_dw[v] + w[i])
{
flag = false;
continue;
}
f.insert(dp_dw[v] + w[i]);
}
}
void DFS_up(int u, int p)
{
long long g[2];
int t[2];
g[0] = g[1] = -1e18;
t[0] = t[1] = -1;
for (auto [v, i] : adj[u])
{
if (v == p)
{
continue;
}
dp_up[v] = dp_up[u] + w[i ^ 1];
for (int j = 1; j >= 0; -- j)
{
if (dp_dw[v] + w[i] >= g[j])
{
for (int k = 0; k < j; ++ k)
{
g[k] = g[k + 1];
t[k] = t[k + 1];
}
g[j] = dp_dw[v] + w[i];
t[j] = v;
break;
}
}
}
for (auto [v, i] : adj[u])
{
if (v == p)
{
continue;
}
for (int j = 1; j >= 0; -- j)
{
if (t[j] != v)
{
dp_up[v] = max(dp_up[v], g[j] + w[i ^ 1]);
break;
}
}
DFS_up(v, u);
}
}
void DFS(int u, int p)
{
res[1] = min(res[1], sum_all - sum);
int cur = 1;
long long t = 0;
for (multiset<long long> :: reverse_iterator i = f.rbegin(); i != f.rend(); ++ i)
{
++cur;
t += *i;
res[cur] = min(res[cur], sum_all - sum - t);
}
while(cur < n)
{
++cur;
res[cur] = min(res[cur], sum_all - sum - t);
}
for (auto [v, i] : adj[u])
{
if (v == p)
{
continue;
}
sum -= w[i ^ 1];
sum += w[i];
f.erase(f.find(dp_up[v] - w[i ^ 1]));
f.erase(f.find(dp_dw[v] + w[i]));
f.insert(dp_up[v]);
f.insert(dp_dw[v]);
DFS(v, u);
sum += w[i ^ 1];
sum -= w[i];
f.insert(dp_up[v] - w[i ^ 1]);
f.insert(dp_dw[v] + w[i]);
f.erase(f.find(dp_up[v]));
f.erase(f.find(dp_dw[v]));
}
}
void sub4()
{
memset(res, 0x3f, sizeof(res));
DFS_dw(1, 0);
f.insert(dp_dw[1]);
f.insert(0);
DFS_up(1, 0);
DFS(1, 0);
while(q--)
{
int x;
cin >> x;
cout << res[x] << '\n';
}
}
void solve()
{
if (n <= 16)
{
sub1();
return ;
}
if (n <= 2000)
{
sub4();
return ;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
Compilation message
designated_cities.cpp: In function 'bool DFS_brute(int, int)':
designated_cities.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
39 | }
| ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:215:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
215 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
13136 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
13108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
13200 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
13136 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
13108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
13136 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
