Submission #979270

#TimeUsernameProblemLanguageResultExecution timeMemory
979270michifiedTraining (IOI07_training)C++17
100 / 100
32 ms1028 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; struct edge_t { int from, to, cost, c1, c2, cont; }; struct node_t { int par, depth; map<int, int> childs; vector<edge_t> es; vector<int> dp; }; int n, m; vector<node_t> tree; vector<vector<int>> adj; vector<edge_t> nontree; void rootTree(int cur, int par) { node_t& u = tree[cur]; if (par != -1) { u.par = par; u.depth = tree[par].depth + 1; } for (int v : adj[cur]) { if (v == par) continue; u.childs[v] = u.childs.size(); rootTree(v, cur); } } pair<int, pair<int, int>> lca(int a, int b) { int c1 = -1, c2 = -1; while (tree[a].depth > tree[b].depth) { if (tree[a].par == b) c1 = a; a = tree[a].par; } while (a != b) { if (tree[a].par == tree[b].par) { c1 = a; c2 = b; } a = tree[a].par; b = tree[b].par; } return mp(a, mp(c1, c2)); } void dfs(int cur) { node_t& u = tree[cur]; u.dp.resize(1 << u.childs.size(), 0); for (auto& v : u.childs) dfs(v.first); int tmp, i, hi; for (edge_t& e : u.es) { tmp = e.from; if (tmp != cur) { e.cont += tree[tmp].dp.back(); while (tree[tmp].par != cur) { e.cont += tree[tree[tmp].par].dp[(tree[tree[tmp].par].dp.size() - 1) - (1 << tree[tree[tmp].par].childs[tmp])]; tmp = tree[tmp].par; } } if (e.c2 == -1) continue; tmp = e.to; if (tmp != cur) { e.cont += tree[tmp].dp.back(); while (tree[tmp].par != cur) { e.cont += tree[tree[tmp].par].dp[(tree[tree[tmp].par].dp.size() - 1) - (1 << tree[tree[tmp].par].childs[tmp])]; tmp = tree[tmp].par; } } } for (i = 0; i < u.dp.size(); i++) { for (auto& v : u.childs) { if (i & (1 << v.second)) u.dp[i] += tree[v.first].dp.back(); } hi = 0; for (edge_t& e : u.es) { if ((i & (1 << u.childs[e.c1])) == 0 or (e.c2 != -1 and (i & (1 << u.childs[e.c2])) == 0)) continue; hi = max(hi, e.cont + u.dp[i - (1 << u.childs[e.c1]) - (e.c2 == -1 ? 0 : (1 << u.childs[e.c2]))]); } u.dp[i] = max(u.dp[i], hi); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; tree.resize(n + 1); adj.resize(n + 1); int tu, tv, tc, i, tot = 0; pair<int, pair<int, int>> res; for (i = 0; i < m; i++) { cin >> tu >> tv >> tc; if (tc == 0) { adj[tu].pb(tv); adj[tv].pb(tu); } else { nontree.pb({tu, tv, tc, -1, -1}); tot += tc; } } rootTree(1, -1); for (edge_t& e : nontree) { if ((tree[e.from].depth + tree[e.to].depth) % 2 == 1) continue; if (tree[e.from].depth < tree[e.to].depth) swap(e.from, e.to); res = lca(e.from, e.to); tree[res.first].es.pb({e.from, e.to, e.cost, res.second.first, res.second.second, e.cost}); } dfs(1); cout << tot - tree[1].dp.back(); return 0; }

Compilation message (stderr)

training.cpp: In function 'void dfs(int)':
training.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (i = 0; i < u.dp.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...