Submission #1276607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276607		behesht	Tug of War (BOI15_tug)	C++20	100 / 100	1635 ms	119744 KiB

tug

#include <bits/stdc++.h>
 
#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1
 
using namespace std;
 
const int INF = 1e18 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 2e6 + 24 + (34 / 10); // 34 ---> 35
const int MOD = 1e9 + 7;
 
int p[MAXN], dp[2][MAXN];
set <int> adj[MAXN];
set <arr(2)> s;
bool vis[MAXN];
vector <int> e;
 
void del(int u){
 
	for(auto v : adj[u]){
		int sz = adj[v].size();
		s.erase({sz, v});
 
		adj[v].erase(u);
 
		if(!adj[v].empty())
			s.insert({sz - 1, v});
	}
 
	adj[u].clear();
}
 
void dfs(int u){
 
	vis[u] = 1;
	e.pb(u);
 
	for(auto v : adj[u])
		if(!vis[v])
			dfs(v);
}
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n, k;
	cin >> n >> k;
 
	int all = 0;
 
	for(int i = 0; i < 2 * n; i++){
		int a, b;
		cin >> a >> b >> p[i];
 
		a--;
		b--;
 
		a += 2 * n;
		b += 3 * n;
 
		adj[i].insert(a);
		adj[a].insert(i);
		
		adj[i].insert(b);
		adj[b].insert(i);
 
		all += p[i];
	}
 
	for(int i = 2 * n; i < 4 * n; i++)
		if(!adj[i].empty()){
			int sz = adj[i].size();
			s.insert({sz, i});
		}
 
	int sm = 0;
	
	while(!s.empty()){
		auto [sz, u] = *s.begin();
 
		if(sz > 1)
			break;
 
		auto v = *adj[u].begin();
		vis[u] = vis[v] = 1;
 
		if(u < 3 * n)	
			sm += p[v];
 
		del(v);
	}
 
	for(int i = 2 * n; i < 4 * n; i++)
		if(adj[i].empty() && !vis[i]){
			cout << "NO" << endl;
			return 0;
		}
 
	vector <int> vec;
 
	for(int i = 0; i < 2 * n; i++){
		if(!vis[i]){
			
			e.clear();
			dfs(i);
			e.pb(i);
 
			// d1(i);
			// for(auto v : e)
			// 	cout << v + 1 <<"  ";
			// 	cout << endl;
 
			int eli = 1;
			arr(2) res;
 
			for(int t = 0; t < 2; t++){
				eli *= -1;
				int val = 0;
 
				for(int j = 1; j < e.size(); j += 2){
					if(e[j] < 3 * n)
						val += p[e[j + eli]];
				}
 
				res[t] = val;
			}
 
			// d2(res[0], res[1]);
			// cout << endl;
 
			if(res[0] > res[1])
				swap(res[0], res[1]);
 
			sm += res[0];
			vec.pb(res[1] - res[0]);
		}
	}
 
	vec.pb(INF);
	sort(vec.begin(), vec.end());
	
	vector <arr(2)> a;
	int cnt = 1;
 
	for(int i = 1; i < vec.size(); i++){
 
		if(vec[i] == vec[i - 1])
			cnt++;
 
		else{
			a.pb({vec[i - 1], cnt});
			cnt = 1;
		}
	}
 
	dp[0][sm] = 1;
 
	for(int i = 1; i < a.size(); i++){
 
		for(int j = 1; j <= n * 20; j++)
			dp[i & 1][j] = 0;
 
		for(int j = 1; j <= n * 20; j++){
			dp[i & 1][j] = dp[(i - 1) & 1][j];
 
			if(j >= a[i][0])
				dp[i & 1][j] += dp[i & 1][j - a[i][0]];
 
			if(j >= (a[i][1] + 1) * a[i][0])
				dp[i & 1][j] -= dp[(i - 1) & 1][j - (a[i][1] + 1) * a[i][0]];
 
			dp[i & 1][j] %= MOD;
			dp[i & 1][j] += MOD;
			dp[i & 1][j] %= MOD;
		}
	}
 
	for(int j = 0; j <= n * 20; j++)
		if(dp[(a.size() - 1) & 1][j] && abs(all - 2 * j) <= k){
			cout << "YES" << endl;
			return 0;
		}
 
	cout << "NO" << endl;
}
 
// Ey To Bahane! :_)))
 
// -------------<3------------- //
/*
Magasan dor shirini: 
 
1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 
 
*/

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29