Submission #1193021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193021		_rain_	Tug of War (BOI15_tug)	C++20	100 / 100	501 ms	53492 KiB

tug

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)1e6;
multiset<pair<int,int>>ke[N+2];
bool vis[N+2]={};
int n,k,tot=0;
bitset<600002>dp;
vector<int>item;

void dfs(int u){
	vis[u]=true;
	if (ke[u].size()==0) return;
	pair<int,int>v=*ke[u].begin();
	tot+=v.second;
	if (!vis[v.first]){
		ke[u].clear();
		ke[v.first].erase(ke[v.first].find({u,-v.second}));
		dfs(v.first);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
//	freopen("main.inp","r",stdin);
	
	cin>>n>>k;
	for(int i=1;i<=2*n;++i){
		int l,r,s; cin>>l>>r>>s;
		ke[l].insert({r+n,s});
		ke[r+n].insert({l,-s});
	}
	for(int i=1;i<=2*n;++i) if (ke[i].size()==0) {
		cout<<"NO";
		return 0;
	}
	queue<int>q;
	for(int i=1;i<=2*n;++i){
		if (ke[i].size()==1) q.push(i);
	}
	int sum_tot=0;
	while (q.size()){
		int u=q.front(); q.pop();
		if (ke[u].size()==0){
			cout<<"NO";
			return 0;
		}
		pair<int,int>x=*ke[u].begin();
		sum_tot+=x.second;
		ke[u].clear();
		ke[x.first].erase(ke[x.first].find({u,-x.second}));
		if (ke[x.first].size()==1) q.push(x.first);		
	}
	for(int i=1;i<=2*n;++i){
		if (!vis[i] && ke[i].size()){
			tot=0;
			assert(ke[i].size()==2);
			ke[i].erase(ke[i].begin());
			dfs(i);
			if (tot!=0) item.push_back(abs(tot));
		}
	}
	int sm=accumulate(item.begin(),item.end(),0);
	dp[0]=1;
	for(auto&x:item) dp|=(dp<<x);
	for(int i=0;i<=sm;++i){
		if (dp[i] && abs(2*i-sm+sum_tot)<=k){
			cout<<"YES\n";
			return 0;
		}
	}
	cout<<"NO";
	exit(0);
}

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