| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 699041 | 2023-02-15T12:23:55 Z | caganyanmaz | Training (IOI07_training) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define mt make_tuple #define mp make_pair #define pb push_back #define printv(v) for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << "\n" using namespace std; struct SegTree { int n; vector<int> data; SegTree(int n) : n(n), data(2*n, 0) {} void build(const vector<int>& cost_sums) { for (int i = 0; i < n; i++) data[i+n] = cost_sums[i]; for (int i = n-1; i > 0; i--) data[i] = data[i<<1] + data[i<<1|1]; } int get(int l, int r) { int res = 0; for (l+=n, r+=n; l < r; l>>=1,r>>=1) { if (l&1) res += data[l++]; if (r&1) res += data[--r]; } return res; } }; int main() { int n, m; cin >> n >> m; vector<vector<int>> og(n); // Graph with only paved roads vector<tuple<int, int, int>> edges; // Only unpaved roads for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--, b--; if (c) { edges.pb(mt(a, b, c)); } else { og[a].pb(b); og[b].pb(a); } } vector<int> mapping(n); int node = 0; while (og[node].size() == 2) node++; mapping[node] = 0; for (int j = 1, i = og[node][0], prev = node; j < n; j++) { mapping[i] = j; if (og[i].size() == 1) break; int _new = (og[i][0] == prev) ? og[i][1] : og[i][0]; prev = i; i = _new; } vector<vector<pair<int, int>>> forward_edges(n); int total_cost = 0; for (auto [a, b, c] : edges) { a = mapping[a], b = mapping[b]; if (a > b) swap(a, b); if ((b-a)&1) total_cost += c; else forward_edges[a].pb(mp(b, c)); } vector<int> cost_sums(n); for (int i = 0; i < n; i++) { int sum = 0; for (auto [_, c] : forward_edges[i]) sum += c; cost_sums[i] = sum; } SegTree st(n); st.build(cost_sums); vector<int> dp(n, 1e8); dp[0] = 0; for (int i = 0; i < n-1; i++) { if (i != n-1) dp[i+1] = min(dp[i+1], dp[i] + cost_sums[i]); for (auto [r, c] : forward_edges[i]) dp[r] = min(dp[r], dp[i] + st.get(i, r) - c); } cout << (total_cost + dp[n-1]) << "\n"; }