| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 503063 |
2022-01-07T04:46:42 Z |
tabr |
Training (IOI07_training) |
C++17 |
|
300 ms |
51184 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct dsu {
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
inline int get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = get(p[x]);
}
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
if (sz[x] > sz[y]) {
swap(x, y);
}
p[x] = y;
sz[y] += sz[x];
return true;
}
inline bool same(int x, int y) {
return (get(x) == get(y));
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
dsu uf(2 * n);
vector<vector<int>> g(n);
vector<tuple<int, int, int>> edges;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
if (c == 0) {
g[a].emplace_back(b);
g[b].emplace_back(a);
uf.unite(a, b + n);
uf.unite(a + n, b);
} else {
edges.emplace_back(a, b, c);
}
}
vector<tuple<int, int, int>> new_edges;
int ans = 0;
for (auto [a, b, c] : edges) {
ans += c;
if (uf.same(a, b)) {
new_edges.emplace_back(a, b, c);
}
}
swap(edges, new_edges);
m = (int) edges.size();
vector<vector<int>> d(n);
for (int i = 0; i < m; i++) {
auto [a, b, c] = edges[i];
d[a].emplace_back(i);
d[b].emplace_back(i);
}
vector<vector<int>> from(1 << 10);
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j < 10; j++) {
if (i & (1 << j)) {
continue;
}
from[i | (1 << j)].emplace_back(1 << j);
for (int k = j + 1; k < 10; k++) {
if (i & (1 << k)) {
continue;
}
from[i | (1 << j) | (1 << k)].emplace_back((1 << j) | (1 << k));
}
}
}
vector<unordered_map<int, int>> dp(n);
function<void(int, int)> dfs = [&](int v, int p) {
vector<int> ch;
unordered_map<int, vector<int>> mp;
for (int to : g[v]) {
if (to == p) {
continue;
}
dfs(to, v);
for (auto [id, cost] : dp[to]) {
if (id != -1) {
mp[id].emplace_back((int) ch.size());
}
}
ch.emplace_back(to);
}
int sz = (int) ch.size();
vector<int> f(1 << sz);
for (int i = 0; i < sz; i++) {
f[1 << i] = dp[ch[i]][-1];
}
for (auto [id, u] : mp) {
if (u.size() == 2) {
f[(1 << u[0]) + (1 << u[1])] = max(f[(1 << u[0]) + (1 << u[1])], dp[ch[u[0]]][id] + dp[ch[u[1]]][id] + get<2>(edges[id]));
}
}
for (int id : d[v]) {
auto u = mp[id];
if (u.size() == 1) {
f[1 << u[0]] = max(f[1 << u[0]], dp[ch[u[0]]][id] + get<2>(edges[id]));
mp[id].emplace_back(-1);
}
}
for (int i = 0; i < (1 << sz); i++) {
for (int j : from[i]) {
f[i] = max(f[i], f[j] + f[i ^ j]);
}
}
dp[v][-1] = f.back();
for (int id : d[v]) {
auto u = mp[id];
if (u.size() == 0) {
dp[v][id] = f.back();
}
}
for (auto [id, u] : mp) {
if (u.size() == 1) {
dp[v][id] = f[(1 << sz) - (1 << u[0]) - 1] + dp[ch[u[0]]][id];
}
}
};
dfs(0, -1);
ans -= dp[0][-1];
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
14632 KB |
Output is correct |
| 2 |
Correct |
116 ms |
16364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
4 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1400 KB |
Output is correct |
| 3 |
Correct |
20 ms |
3424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
3560 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1996 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
30 ms |
5064 KB |
Output is correct |
| 3 |
Execution timed out |
343 ms |
51184 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
17988 KB |
Output is correct |
| 2 |
Execution timed out |
347 ms |
50796 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
