| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 503068 |
2022-01-07T05:20:48 Z |
tabr |
Training (IOI07_training) |
C++17 |
|
258 ms |
50956 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));
}
};
vector<int> g[1010];
vector<int> d[1010];
vector<int> from[1030];
unordered_map<int, int> dp[1010];
int f[1030];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
dsu uf(2 * 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();
for (int i = 0; i < m; i++) {
auto [a, b, c] = edges[i];
d[a].emplace_back(i);
d[b].emplace_back(i);
}
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));
}
}
}
function<void(int, int)> dfs = [&](int v, int p) {
vector<int> ch;
unordered_map<int, pair<int, int>> mp;
for (int to : g[v]) {
if (to == p) {
continue;
}
dfs(to, v);
for (auto [id, cost] : dp[to]) {
if (id != -1) {
if (mp.count(id)) {
mp[id].second = (int) ch.size();
} else {
mp[id] = make_pair((int) ch.size(), -1);
}
}
}
ch.emplace_back(to);
}
int sz = (int) ch.size();
memset(f, 0, 4 << sz);
for (int i = 0; i < sz; i++) {
f[1 << i] = dp[ch[i]][-1];
}
for (auto [id, u] : mp) {
if (u.second != -1) {
f[(1 << u.first) | (1 << u.second)] = max(f[(1 << u.first) | (1 << u.second)], dp[ch[u.first]][id] + dp[ch[u.second]][id] + get<2>(edges[id]));
}
}
for (int id : d[v]) {
if (!mp.count(id)) {
continue;
}
auto &u = mp[id];
if (u.second == -1) {
f[1 << u.first] = max(f[1 << u.first], dp[ch[u.first]][id] + get<2>(edges[id]));
u.second = -2;
}
}
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[(1 << sz) - 1];
for (int id : d[v]) {
if (!mp.count(id)) {
dp[v][id] = f[(1 << sz) - 1];
}
}
for (auto [id, u] : mp) {
if (u.second == -1) {
dp[v][id] = f[(1 << sz) - (1 << u.first) - 1] + dp[ch[u.first]][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 |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
14520 KB |
Output is correct |
| 2 |
Correct |
91 ms |
16392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
716 KB |
Output is correct |
| 2 |
Correct |
2 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1356 KB |
Output is correct |
| 3 |
Correct |
17 ms |
3332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
3440 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
22 ms |
5000 KB |
Output is correct |
| 3 |
Correct |
241 ms |
50956 KB |
Output is correct |
| 4 |
Correct |
38 ms |
8952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
17828 KB |
Output is correct |
| 2 |
Correct |
258 ms |
50716 KB |
Output is correct |
| 3 |
Correct |
94 ms |
18940 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1952 KB |
Output is correct |
