oj.uz

답안 #699043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699043 2023-02-15T12:25:22 Z caganyanmaz Training (IOI07_training) C++14
30 / 100
 4 ms 560 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";

}

Compilation message

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 244 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 448 KB Output is correct

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 440 KB Output isn't correct
2 Halted 0 ms 0 KB -