oj.uz

Submission #726151

# Submission time Handle Problem Language Result Execution time Memory
726151 2023-04-18T14:46:36 Z dozer Tug of War (BOI15_tug) C++14
18 / 100
 128 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 60005

const int modulo = 1e9 + 7;


set<int> adj[N];
int l[N], r[N], w[N], done[N];

int32_t main()
{
	fastio();


	int n, k;
	cin>>n>>k;
	int all = 0;
	for (int i = 1; i <= 2 * n; i++)
	{
		cin>>l[i]>>r[i]>>w[i];
		adj[l[i]].insert(i);
		adj[r[i] + n].insert(i);
		all += w[i];
	}

	int sum = 0;
	queue<int> q;
	for (int i = 1; i <= 2 * n; i++)
		if (adj[i].size() == 1) q.push(i);

	int flag = 0;
	while(!q.empty())
	{
		int top = q.front();
		q.pop();
		done[top] = 1;
		if (adj[top].empty())
		{
			flag = 1;
			break;
		}

		if (top <= n) sum += w[*adj[top].begin()];
		else sum -= w[*adj[top].begin()];

		for (auto i : adj[top])
		{
			int to = l[i];
			if (to == top) to = r[i] + n;
			adj[to].erase(i);
			if (adj[to].size() == 1) q.push(to);
		}
	}	

	if (flag)
	{
		cout<<"NO\n";
		return 0;
	}

	vector<int> v;
	for (int i = 1; i <= 2 * n; i++)
	{
		if (done[i]) continue;
		if (adj[i].empty())
		{
			flag = 1;
			break;
		}
		int curr = i, steps = 0, tot = 0;
		while(done[curr] == 0 && !adj[curr].empty())
		{
			done[curr] = 1;
			if (adj[curr].size() > 2)
			{
				flag = 1;
				break;
			}
			int ind = *adj[curr].begin();
			if (steps % 2) tot -= w[ind];
			else tot += w[ind];
			steps++;
			int to = l[ind];
			if (to == curr) to = r[ind] + n;
			adj[to].erase(ind);
			adj[curr].erase(ind);
			curr = to;
		}
		v.pb(abs(tot));	
	}
	if (flag)
	{
		cout<<"NO\n";
		return 0;
	}
	v.pb(0);
	

	int dp[v.size() + 5][2 * all + 5];
	memset(dp, 0, sizeof(dp));
	
	sort(v.rbegin(), v.rend());
	dp[0][all] = 1;
	for (int i = 0; i < (int)v.size(); i++)
	{
		for (int j = 0; j <= 2 * all - v[i]; j++)
		{
			dp[i + 1][j + v[i]] |= dp[i][j];
			if (j >= v[i]) dp[i + 1][j - v[i]] |= dp[i][j];
		}
	}


	sum = abs(sum);
	
	for (int i = 0; i <= 2 * all; i++)
		if (dp[v.size()][i] && abs(sum + (i - all)) <= k) flag = 1;


	if (flag) cout<<"YES\n";
	else cout<<"NO\n";

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3152 KB Output is correct
4 Correct 2 ms 3144 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 2 ms 3152 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3144 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3144 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 2 ms 3156 KB Output is correct
18 Correct 2 ms 3148 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3148 KB Output is correct
22 Correct 2 ms 3156 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 2 ms 3144 KB Output is correct
25 Correct 2 ms 3156 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3152 KB Output is correct
4 Correct 2 ms 3144 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 2 ms 3152 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3144 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3144 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 2 ms 3156 KB Output is correct
18 Correct 2 ms 3148 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3148 KB Output is correct
22 Correct 2 ms 3156 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 2 ms 3144 KB Output is correct
25 Correct 2 ms 3156 KB Output is correct
26 Runtime error 128 ms 262144 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3152 KB Output is correct
4 Correct 2 ms 3144 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 2 ms 3152 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3144 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3144 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 2 ms 3156 KB Output is correct
18 Correct 2 ms 3148 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3148 KB Output is correct
22 Correct 2 ms 3156 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 2 ms 3144 KB Output is correct
25 Correct 2 ms 3156 KB Output is correct
26 Runtime error 128 ms 262144 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -