Submission #705392

#	Time	Username	Problem	Language	Result	Execution time	Memory
705392		alvingogo	Tug of War (BOI15_tug)	C++14	100 / 100	2139 ms	9208 KiB

tug

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

/* ok, bitset!!!


wait, is it possible that their's only one contestent that wants one kind of graph?

ok, let's just eliminate these cases, because sum_deg = 8n and we have4n points to consider if we make a graph from people i to left l_i and right r_i.
if we consider all the people and make a graph

if someone's deg = 1 then we know that we should take it and its neighbor, and wow, that's a matching problem!

first: find out if it has a perfect matching
iterate all the nodes deg = 1
we know people's deg = 2 so that L and R can do this

SAMITorz 

second: bitsetorz

rings, choose the odd edges or the even edges, and do knapsack to find out if we can make the difference less then k
i want to make it like "b |= b<<k" or else

maybe the right side should have strength in [a,b];
we can find out how much we add to the right side

given an array A, an int x, for all elements C, you can add C to x or subtract C to x, find out if you can make abs(x) less then or equal to k 
isn't it knapsack?

30000*30000*2*20/64 = 9e8 :EEEEE:
CF 1e9/s la
or greedy
greedy?

fine, since it's the only method i can figure out
let's gooooooooooo :TLEthinking:
*/


bitset<1200007> bt;

vector<vector<pair<int,int> > > g;
int main(){
    AquA;
	bt[0]=1;
	int n,k;
	cin >> n >> k;
	g.resize(4*n);
	vector<int> deg(4*n),vis(4*n);
	int sum=0;
	for(int i=0;i<2*n;i++){
		int a,b,s;
		cin >> a >> b >> s;
		a--;
		b--;
		sum+=s;
		g[a+2*n].push_back({i,s});
		g[i].push_back({a+2*n,s});
		g[b+3*n].push_back({i,s});
		g[i].push_back({b+3*n,s});
		deg[i]=2;
		deg[a+2*n]++;
		deg[b+3*n]++;
	}
	queue<int> q;
	for(int i=2*n;i<4*n;i++){
		if(deg[i]==1){
			q.push(i);
		}
		if(deg[i]==0){
			cout << "NO\n";
			return 0;
		}
	}
	while(q.size()){
		auto h=q.front();
		q.pop();
		int flag=0;
		for(auto y:g[h]){
			if(!vis[y.fs]){
				flag=1;
				vis[y.fs]=1;
				if(h>=3*n){
					bt<<=y.sc;
				}
				for(auto z:g[y.fs]){
					deg[z.fs]--;
					if(deg[z.fs]==1){
						q.push(z.fs);
					}
				}
			}
		}
		if(!flag){
			cout << "NO\n";
			return 0;
		}
	}
	for(int i=0;i<2*n;i++){
		if(!vis[i]){
			//dfs time :happy_mention:
			int a=0,b=0;
			for(int x=i,cnt=0,e=-1;cnt==0 || x!=i;cnt=1){
				vis[x]=1;
				for(auto f:g[x]){
					if(f.fs==e){
						continue;
					}
					if(f.fs>=3*n){
						a+=f.sc;
					}
					for(auto y:g[f.fs]){
						if(vis[y.fs] && (y.fs!=i || cnt==0)){

						}
						else{
							if(f.fs>=3*n){
								b+=y.sc;
							}
							x=y.fs;
							e=f.fs;
							break;
						}
					}
					break;
				}
			}
			//cout << a << " " << b << '\n';
			bt=(bt<<a)|(bt<<b);
		}
	}
	for(int i=0;i<=sum;i++){
		if(bt[i]){
			if(abs(i-(sum-i))<=k){
				cout << "YES\n";
				return 0;
			}
		}
	}
	cout << "NO\n";
    return 0;
}

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