| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 598754 |
2022-07-18T23:18:31 Z |
Bobaa |
Training (IOI07_training) |
C++17 |
|
300 ms |
596 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 10;
vector<int> E[N], lca[N], dob;
int id[N], d[N], par[N], pre[N], pst[N], wsk, dp[N][N], dp2[N][5 * N], n, m;
vector<pair<int, pair<int, int>>> edg, edg2;
void dfs1(int v, int p) {
pre[v] = wsk++;
par[v] = p;
d[v] = d[p] + 1;
int sz = E[v].size();
for (int i = 0; i < sz; i++) if (E[v][i] == p) swap(E[v][i], E[v].back());
if (p != 0) E[v].pop_back();
for (int i = 0; i < sz; i++) {
id[E[v][i]] = i;
dfs1(E[v][i], v);
}
pst[v] = wsk;
}
void dfs2(int v) {
for (int u : E[v]) {
dfs2(u);
dp[v][1 << id[u]] = dp2[u][0];
}
for (int e : lca[v]) {
int u = edg[e].second.first, w = edg[e].second.second;
while (par[w] != v) w = par[w];
if (u == v) dp[v][1 << id[w]] = max(edg[e].first + dp2[w][e], dp[v][1 << id[w]]);
else {
while (par[u] != v) u = par[u];
dp[v][(1 << id[u]) + (1 << id[w])] = max(edg[e].first + dp2[u][e] + dp2[w][e], dp[v][(1 << id[u]) + (1 << id[w])]);
}
}
for (int i = 0; i < (1 << E[v].size()); i++) for (int j = i; ; j = (j - 1) & i) {
dp[v][i] = max(dp[v][i], dp[v][j] + dp[v][i - j]);
if (j == 0) break;
}
for (int e : dob) {
if (edg[e].second.first == v && pre[edg[e].second.second] >= pst[v]) dp2[v][e] = dp[v][(1 << E[v].size()) - 1];
if (edg[e].second.second == v) dp2[v][e] = dp[v][(1 << E[v].size()) - 1];
if (par[edg2[e].second.first] == v ^ par[edg2[e].second.second] == v) {
if (par[edg2[e].second.first] == v) {
dp2[v][e] = dp[v][(1 << E[v].size()) - 1 - (1 << id[edg2[e].second.first])] + dp2[edg2[e].second.first][e];
edg2[e].second.first = v;
}
if (par[edg2[e].second.second] == v) {
dp2[v][e] = dp[v][(1 << E[v].size()) - 1 - (1 << id[edg2[e].second.second])] + dp2[edg2[e].second.second][e];
edg2[e].second.second = v;
}
}
}
dp2[v][0] = dp[v][(1 << E[v].size()) - 1];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
int sm = 0;
for (int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w;
sm += w;
edg.push_back({w, {u, v}});
if (w == 0) {
E[u].push_back(v);
E[v].push_back(u);
}
}
dfs1(1, 0);
sort(edg.begin(), edg.end());
for (int i = n - 1; i < m; i++) {
if (pre[edg[i].second.first] > pre[edg[i].second.second]) swap(edg[i].second.first, edg[i].second.second);
int u = edg[i].second.first, v = edg[i].second.second;
if ((d[u] & 1) != (d[v] & 1)) continue;
if (d[u] < d[v]) swap(u, v);
while (d[u] > d[v]) u = par[u];
while (u != v) {
u = par[u];
v = par[v];
}
dob.push_back(i);
lca[u].push_back(i);
}
edg2 = edg;
dfs2(1);
cout << sm - dp2[1][0];
}
Compilation message
training.cpp: In function 'void dfs2(int)':
training.cpp:45:33: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
45 | if (par[edg2[e].second.first] == v ^ par[edg2[e].second.second] == v) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
440 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1085 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
