# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
996857 |
2024-06-11T10:45:48 Z |
Ghetto |
Training (IOI07_training) |
C++17 |
|
300 ms |
236088 KB |
#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const short MAX_N = 1e3 + 5, MAX_M = 4e3 + 5;
short n, m;
vector<short> adj[MAX_N];
struct Edge {
short u, v;
int val;
};
Edge edge[MAX_M];
short n_inds, ind[MAX_N], f_ind[MAX_N];
short depth[MAX_N];
short anc[MAX_N][20];
vector<short> children[MAX_N];
short child_ind[MAX_N];
void dfs1(short u = 1, short par = -1) {
n_inds++, ind[u] = n_inds;
for (short v : adj[u]) {
if (v == par) continue;
anc[v][0] = u, depth[v] = depth[u] + 1;
children[u].push_back(v), child_ind[v] = children[u].size() - 1;
dfs1(v, u);
}
f_ind[u] = n_inds;
}
void precomp1() {
dfs1();
for (short i = 1; i <= 19; i++)
for (short u = 1; u <= n; u++)
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
short lca(short u, short v) {
auto is_anc = [](short u, short v) { return ind[u] <= ind[v] && ind[v] <= f_ind[u]; };
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (short i = 19; i >= 0; i--)
if (anc[u][i] != 0 && !is_anc(anc[u][i], v))
u = anc[u][i];
u = anc[u][0];
return u;
}
int val_sum;
vector<short> paths[MAX_N], path[MAX_M];
void precomp2() {
for (short i = 1; i <= m; i++) {
val_sum += edge[i].val;
short w = lca(edge[i].u, edge[i].v);
short len = depth[edge[i].u] + depth[edge[i].v] - 2 * depth[w] + 1;
if (len % 2 == 0) continue;
paths[w].push_back(i);
}
}
int dp[MAX_N][1 << 10];
int trans[MAX_M];
void dfs2(short u = 1) {
for (short v : children[u]) dfs2(v);
gp_hash_table<short, gp_hash_table<short, vector<short>>> path_children;
for (short i : paths[u]) {
int w = lca(edge[i].u, edge[i].v);
path[i].push_back(w);
int x = edge[i].u;
while (true) {
if (x == w) break;
path[i].push_back(x);
path_children[i][anc[x][0]].push_back(x);
x = anc[x][0];
}
x = edge[i].v;
while (true) {
if (x == w) break;
path[i].push_back(x);
path_children[i][anc[x][0]].push_back(x);
x = anc[x][0];
}
trans[i] = edge[i].val;
for (short v : path[i]) {
if (v == u) continue;
int mask = (1 << children[v].size()) - 1;
for (short w : path_children[i][v]) mask ^= (1 << child_ind[w]);
trans[i] += dp[v][mask];
}
}
for (int mask = 0; mask <= (1 << children[u].size()) - 1; mask++) {
for (short i = 0; i <= (short) children[u].size() - 1; i++) {
if (!(mask & (1 << i))) continue;
short v = children[u][i];
dp[u][mask] += dp[v][(1 << children[v].size()) - 1];
}
for (short i : paths[u]) {
bool halt = false;
for (short v : path_children[i][u])
if (!(mask & (1 << child_ind[v]))) halt = true;
if (halt) continue;
int new_mask = mask;
for (short v : path_children[i][u]) new_mask ^= (1 << child_ind[v]);
dp[u][mask] = max(dp[u][mask], dp[u][new_mask] + trans[i]);
}
}
}
int main() {
// freopen("train.in", "r", stdin);
cin >> n >> m;
short new_m = 0;
for (short i = 1; i <= m; i++) {
short u, v; int val; cin >> u >> v >> val;
if (val == 0) adj[u].push_back(v), adj[v].push_back(u);
else new_m++, edge[new_m] = {u, v, val};
}
m = new_m;
precomp1();
precomp2();
dfs2();
int ans = val_sum - dp[1][(1 << children[1].size()) - 1];
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
43368 KB |
Output is correct |
2 |
Correct |
82 ms |
14936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2908 KB |
Output is correct |
2 |
Correct |
3 ms |
3300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
4364 KB |
Output is correct |
2 |
Correct |
9 ms |
5992 KB |
Output is correct |
3 |
Correct |
45 ms |
17484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
7560 KB |
Output is correct |
2 |
Correct |
31 ms |
6728 KB |
Output is correct |
3 |
Correct |
17 ms |
5180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
4572 KB |
Output is correct |
2 |
Correct |
31 ms |
10132 KB |
Output is correct |
3 |
Execution timed out |
552 ms |
236088 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
51284 KB |
Output is correct |
2 |
Execution timed out |
356 ms |
89680 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |