Submission #952570

#	Time	Username	Problem	Language	Result	Execution time	Memory
952570		PM1	Tug of War (BOI15_tug)	C++17	23 / 100	320 ms	7252 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=3e4+5;
int n,k,f[mxn*2][2],ans=0,st[mxn*2],res=0;
set<int>s[mxn*2];
set<pair<int,int> >g;
bool mark[mxn*2];
vector<int>nk;
void dfs(int z,int dis){
	mark[z]=1;
	int x=*s[z].begin();
	res+=(dis&1)?-st[x]:st[x];
	s[z].erase(x);
	int y=z^f[x][0]^f[x][1];
	s[y].erase(x);
	if(!mark[y])
		dfs(y,dis+1);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n*2;i++){
		int x,y;
		cin>>x>>y>>st[i];
		s[x].insert(i);
		s[y+mxn].insert(i);
		f[i][0]=x;
		f[i][1]=y+mxn;
	}
	for(int i=1;i<=n;i++){
		g.insert({s[i].size(),i});
		g.insert({s[i+mxn].size(),i+mxn});
	}
	while(g.size() && g.begin()->fr<2){
		if(g.begin()->fr<=0){
			cout<<"NO";
			return 0;
		}
		int x=g.begin()->sc;
		int y=*s[x].begin();
		s[x].erase(y);
		int z=x^f[y][0]^f[y][1];
		assert(s[z].find(y)!=s[z].end());
		s[z].erase(y);
		g.erase({1,x});
		g.erase({s[z].size()+1,z});
		g.insert({s[z].size(),z});
		if(x>mxn)ans+=st[y];
		else ans-=st[y];
	}
	for(int i=1;i<=n;i++){
		if(!s[i].size() || mark[i])continue;
		res=0;
		dfs(i,0);
		nk.push_back(res);
	}
	for(int i=1+mxn;i<=n+mxn;i++){
		if(!s[i].size() || mark[i])continue;
		res=0;
		dfs(i,0);
		if(res<0)res*=-1;
		nk.push_back(res);
	}
	const int gg=20*30000+5,ggg=gg*2;
	bitset<ggg>b;
	b[gg]=1;
	for(int i=1;i<=nk.size();i++){
		int x=nk[i-1];
		b=((b<<x)|(b>>x));
	}
	for(int i=gg-k+ans;i<=gg+k+ans;i++){
		if(b[i]){
			cout<<"YES";
			return 0;
		}
	}
	cout<<"NO";
	return 0;

}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=1;i<=nk.size();i++){
      |              ~^~~~~~~~~~~

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