Submission #772884

#	Time	Username	Problem	Language	Result	Execution time	Memory
772884		Ahmed57	Tug of War (BOI15_tug)	C++17	100 / 100	1061 ms	10960 KiB

tug

#include <bits/stdc++.h>
using namespace std;
const int mxN=6e4;
int n, k, l[mxN], r[mxN], s[mxN], dp0;
set<int> pc[mxN];
bitset<20*mxN+1> dp;
queue<int> qu;
vector<int> vc;
void fk(){
	cout << "NO";
	exit(0);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	n*=2;
	for(int i=0; i<n; ++i) {
		cin>>l[i]>>r[i]>>s[i], --l[i], r[i]+=n/2-1;
		pc[l[i]].insert(i);
		pc[r[i]].insert(i);
	}
	for(int i=0; i<n; ++i) {
		if(!pc[i].size())fk();
		else if(pc[i].size()==1)qu.push(i);
	}
	dp0=10*n;
	while(qu.size()){
		int u=qu.front();
		if(!pc[u].size())fk();
		qu.pop();
		int a=*pc[u].begin(),v=u^l[a]^r[a];
		dp0+=u<n/2?s[a]:-s[a];
		pc[v].erase(a);
		if(pc[v].size()==1)qu.push(v);
	}
	for(int i=0;i<n;++i) {
		if(pc[i].size()<2)
			continue;
		int c=0;
		for(int j=i; pc[j].size(); ) {
			int a=*pc[j].begin();
			c+=j<n/2?s[a]:-s[a];
			pc[l[a]].erase(a);
			pc[r[a]].erase(a);
			j^=l[a]^r[a];
		}
		c=abs(c);
		dp0-=c;
		vc.push_back(2*c);
	}
	dp[dp0]=1;
	for(int c:vc)dp|=dp<<c;
	bool ok=0;
	for(int i=10*n-k;i<=10*n+k&&!ok;++i)
		ok=dp[i];
	if(!ok)fk();
	cout << "YES";
}

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