oj.uz

Submission #677056

# Submission time Handle Problem Language Result Execution time Memory
677056 2023-01-02T08:04:53 Z Melika0gh Tug of War (BOI15_tug) C++17
23 / 100
 35 ms 13748 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double   ld;
#define sync	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pb		push_back
#define pii		pair<int, int>
#define mp		make_pair
#define fi		first
#define se		second


const int maxn = 3e4 + 10;
int n, k, lst;
vector<int> adj[maxn * 2], tmp[maxn * 2];
vector<int> cycle[maxn];
int s[maxn * 2], l[maxn * 2], r[maxn * 2], vis[maxn * 2], comp[maxn * 2], ans, N, E;
bool mark[maxn * 2];
vector<int> res, path;

void Dfs(int v, int p)
{
	vis[v] = 1;
	comp[v] = lst;
	int tmp_res = 0;
	for(int id : adj[v])
	{
		if(id == p)
			continue;
		
		int u = l[id] + r[id] - v;
		if(!vis[u])
		{
			path.pb(id);
		//	cout << v << " - " << u << " : " << path.size() << endl;
			Dfs(u, id);
			path.pop_back();
		}
		else if(vis[u] == 1)
		{
			//cout << id << endl;
			mark[l[id]] = mark[r[id]] = 1;
			int pnt = path.size();
			//cout << v << " - " << u << " : " << pnt << endl;
			if(pnt % 2)
				tmp_res += s[id];
			else
				tmp_res -= s[id];
			
			pnt--;
			while(pnt > 0 && l[path[pnt]] != u && r[path[pnt]] != u)
			{
				mark[l[path[pnt]]] = mark[r[path[pnt]]] = 1;
				if(pnt % 2)
					tmp_res += s[path[pnt]];
				else
					tmp_res -= s[path[pnt]];
					
			//	cout << path[pnt] << " , " ;
				cycle[lst].pb(path[pnt--]);
			}
			mark[l[path[pnt]]] = mark[r[path[pnt]]] = 1;
			cycle[lst].pb(path[pnt]);
			if(pnt % 2)
				tmp_res += s[path[pnt]];
			else
				tmp_res -= s[path[pnt]];
		}
	//	cout << endl;
	}
	if(tmp_res)
	{
		//cout << lst << " : " << tmp_res << endl;
		res.pb(tmp_res);
	}
	vis[v] = 2;
}


void Dfs2(int v, int p)
{
	for(int id : adj[v])
	{
		int u = l[id] + r[id] - v;
		if(mark[u] || u == p)
			continue;
		
		Dfs2(u, v);
		if(u > n)
			ans -= s[id];
		else
			ans += s[id];
	}
	
	return;
}

int main()
{
	sync;
	cin >> n >> k;
	for(int i = 1; i <= 2 * n; i++)
	{
		cin >> l[i] >> r[i] >> s[i];
		r[i] += n;
		adj[l[i]].pb(i);
		adj[r[i]].pb(i);
		
	}
	for(int i = 1; i <= 2 * n; i++)
	{
		if(!vis[i])
		{
			lst++;
			N = 0;
			E = 0;
			Dfs(i, 0);
			E /= 2;
			if(N != E)
			{
				cout << "NO" << '\n';
				return 0;
			}
		}
	}
//	cout << lst << endl;
	for(int i = 1; i <= 2 * n; i++)
	{
		if(mark[i])
		{
			Dfs2(i, 0);
		}
	}
	sort(res.begin(), res.end());
//	reverse(res.begin(), res.end());
//	cout << ans << endl;
	for(int x : res)
	{
		if(ans < 0)
			ans += abs(x);
		else
			ans += 0 - abs(x);
		
	//	cout << x << " : " << ans << endl;
	}
	
	if(abs(ans) > k)
		cout << "NO" << '\n';
	else
		cout << "YES" << '\n';
	
	return 0;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Incorrect 2 ms 3852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Incorrect 2 ms 3852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5328 KB Output is correct
2 Correct 10 ms 5128 KB Output is correct
3 Correct 10 ms 5332 KB Output is correct
4 Correct 10 ms 5128 KB Output is correct
5 Correct 12 ms 5332 KB Output is correct
6 Correct 10 ms 5076 KB Output is correct
7 Correct 9 ms 5364 KB Output is correct
8 Correct 11 ms 5180 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 10 ms 5076 KB Output is correct
11 Correct 9 ms 5436 KB Output is correct
12 Correct 10 ms 5084 KB Output is correct
13 Correct 10 ms 5396 KB Output is correct
14 Correct 10 ms 5464 KB Output is correct
15 Correct 11 ms 5076 KB Output is correct
16 Correct 13 ms 5460 KB Output is correct
17 Correct 11 ms 5124 KB Output is correct
18 Correct 10 ms 5348 KB Output is correct
19 Correct 10 ms 5160 KB Output is correct
20 Correct 14 ms 5404 KB Output is correct
21 Correct 35 ms 13748 KB Output is correct
22 Correct 10 ms 5204 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Incorrect 2 ms 3852 KB Output isn't correct
3 Halted 0 ms 0 KB -