Submission #699043

#	Time	Username	Problem	Language	Result	Execution time	Memory
699043		caganyanmaz	Training (IOI07_training)	C++14	30 / 100	4 ms	560 KiB

training

#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";

}

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:70:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |  for (auto [a, b, c] : edges)
      |            ^
training.cpp:84:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |   for (auto [_, c] : forward_edges[i])
      |             ^
training.cpp:96:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   for (auto [r, c] : forward_edges[i])
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9