Submission #156338

#	Time	Username	Problem	Language	Result	Execution time	Memory
156338		alishahali1382	Tug of War (BOI15_tug)	C++14	100 / 100	1041 ms	10876 KiB

tug

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 60010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, D;
int L[MAXN], R[MAXN], S[MAXN];
bool mark[MAXN];
set<pii> G[MAXN];
vector<int> knapsack;
bitset<MAXN*10> dp;
queue<int> Q;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k;
	for (int i=1; i<=2*n; i++){
		cin>>L[i]>>R[i]>>S[i];
		R[i]+=n;
		G[L[i]].insert({R[i], i});
		G[R[i]].insert({L[i], i});
	}
	for (int i=1; i<=2*n; i++) if (G[i].size()<2) Q.push(i);
	while (Q.size()){
		int v=Q.front();
		Q.pop();
		if (mark[v]) continue ;
		mark[v]=1;
		if (G[v].empty()) kill("NO")
		pii p=*G[v].begin();
		G[v].erase(p);
		if (v<=n) D+=S[p.second];
		else D-=S[p.second];
		G[p.first].erase({v, p.second});
		if (G[p.first].size()<2) Q.push(p.first);
	}
	//debug(D)
	/*
	if (abs(D)<=k) kill("YES")
	kill("NO")*/
	
	for (int i=1; i<=2*n; i++) if (G[i].size()){
		int v=i, tmp=0, z=+1;
		while (1){
			pii p=*G[v].begin();
			G[v].erase(p);
			G[p.first].erase({v, p.second});
			tmp+=z*S[p.second];
			z*=-1;
			v=p.first;
			if (v==i) break ;
		}
		if (tmp<0) tmp=-tmp;
		//debug(tmp)
		D-=tmp;
		knapsack.pb(tmp);
	}
	//debug(D)
	//debugv(knapsack)
	dp.set(0);
	for (int x:knapsack) dp|=(dp<<x);
	for (int i=0; i<MAXN*10; i++) if (dp[i] && abs(2*i+D)<=k) kill("YES")
	kill("NO") 
	
	
	return 0;
}
/*
4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

2 5
1 1 1
1 2 4
2 2 1
2 1 4

*/

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