| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 699041 | caganyanmaz | Training (IOI07_training) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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"; }