Submission #387398

#	Time	Username	Problem	Language	Result	Execution time	Memory
387398		kshitij_sodani	Tug of War (BOI15_tug)	C++14	100 / 100	1656 ms	57544 KiB

tug

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'

int n,k;
int aa[300001];
int bb[300001];
int it[300001];
set<int> pre[300001];
int ans5[300001];
vector<int> adj[300001];
vector<int> adj2[300001];
int vis[300001];
void add(int i,int j){
	adj[2*i+1].pb(2*j);
	adj[2*j+1].pb(2*i);
	/*cout<<2*i+1<<"<<"<<2*j<<endl;
	cout<<2*j+1<<"<<"<<2*i<<endl;
	cout<<endl;*/
}
void add2(int i,int j){
	adj[2*i].pb(2*j+1);
	adj[2*j].pb(2*i+1);
	/*cout<<2*i+1<<"<<"<<2*j<<endl;
	cout<<2*j+1<<"<<"<<2*i<<endl;
	cout<<endl;*/
}
vector<int> ord;
void dfs(int no){
	vis[no]=1;
	pair<int,int> cur2;
	
	cur2.b=(no%2);
	cur2.a=no/2;

	int ind=cur2.a/2;

	if(cur2.b==1){
		if(cur2.a%2==0){
			pre[aa[ind]].erase(cur2.a);
		}
		else{
			pre[bb[ind]].erase(cur2.a);
		}	
	}
	for(auto j:adj[no]){
		if(vis[j]==0){
			dfs(j);
		}
	}
	if(cur2.b==0){
		if(cur2.a%2==0){
			while(pre[aa[ind]].size()){
				int st=0;
				for(auto j:pre[aa[ind]]){
					if(j!=cur2.a){
						//cout<<no<<":"<<j*2+1<<endl;
						dfs(j*2+1);
						st=1;
						break;
					}
				}
				if(st==0){
					break;
				}
			}
		}
		else{
			while(pre[bb[ind]].size()){
				int st=0;
				for(auto j:pre[bb[ind]]){
					if(j!=cur2.a){
					//	cout<<no<<":"<<j*2+1<<endl;
						dfs(j*2+1);
						st=1;
						break;
					}
				}
				if(st==0){
					break;
				}
			}
		}	
	}
	



	ord.pb(no);
}
int cur=0;
void dfs2(int no){
	vis[no]=cur;
	pair<int,int> cur;
	
	cur.b=(no%2);
	cur.a=no/2;

	int ind=cur.a/2;

	if(cur.b==0){
		if(cur.a%2==0){
			pre[aa[ind]].erase(cur.a);
		}
		else{
			pre[bb[ind]].erase(cur.a);
		}	
	}
	for(auto j:adj2[no]){
		if(vis[j]==0){
			dfs2(j);
		}
	}
	if(cur.b==1){
		if(cur.a%2==0){
			while(pre[aa[ind]].size()){
				int st=0;
				for(auto j:pre[aa[ind]]){
					if(j!=cur.a){
						dfs2(j*2);
						st=1;
						break;
					}
				}
				if(st==0){
					break;
				}
			}
		}
		else{
			while(pre[bb[ind]].size()){
				int st=0;
				for(auto j:pre[bb[ind]]){
					if(j!=cur.a){
						dfs2(j*2);
						st=1;
						break;
					}
				}
				if(st==0){
					break;
				}
			}
		}	
	}
}

vector<int> adj3[300001];
int coo[300001];
int kk[300001];
vector<pair<int,int>> pp;
void dfs3(int no){
	kk[no]=1;
	pp.pb({no,it[ans5[no]]});
	for(auto j:adj3[no]){
		if(kk[j]==0){
			dfs3(j);
		}
	}
}
bool dp[2001][2001*2*20];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<2*n;i++){
		cin>>aa[i]>>bb[i]>>it[i];
		aa[i]--;
		bb[i]--;
		bb[i]+=n;
		pre[aa[i]].insert(2*i);
		pre[bb[i]].insert(2*i+1);
		add(i*2,i*2+1);
	}
	/*if(n<=10){
		int ans=0;
		for(int i=0;i<(1<<(2*n));i++){
			vector<int> ss;
			vector<int> tt;
			for(int j=0;j<2*n;j++){
				if((1<<j)&i){
					ss.pb(j);
				}
				else{
					tt.pb(j);
				}
			}
			if(ss.size()==n){
				set<int> xx;
				set<int> yy;
				int su=0;
				for(auto j:ss){
					su+=it[j];
					xx.insert(aa[j]);
				}
				for(auto j:tt){
					su-=it[j];
					yy.insert(bb[j]);
				}
				if(abs(su)<=k and xx.size()==n and yy.size()==n){
					ans=1;
				}

			}
		}

		if(ans){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
		return 0;
	}*/

	/*for(int i=0;i<2*n;i++){
		for(auto jj:pre[aa[i]]){
			int j=jj/2;
			if(j!=i){
			//	cout<<i<<":"<<j<<endl;
				//not(j*2) or not(i*2)
			//	add2(i*2,j*2);
			//	continue;
				adj[(j*2)*2].pb(2*(2*i)+1);
				adj[(i*2)*2].pb((j*2)*2+1);
			}
		}
		for(auto jj:pre[bb[i]]){
			int j=jj/2;
			if(j!=i){
			//cout<<i<<","<<j<<endl;
			//	add2(i*2+1,j*2+1);
				//continue;
				adj[(j*2+1)*2].pb(2*(2*i+1)+1);
				adj[(i*2+1)*2].pb((j*2+1)*2+1);
			}
		}
	}
	*/
	for(int i=0;i<8*n;i++){
		for(auto j:adj[i]){
			adj2[j].pb(i);
			//cout<<j<<".."<<i<<endl;
		}
	}


	for(int i=0;i<8*n;i++){
		if(vis[i]==0){
			dfs(i);
		}
	}
	reverse(ord.begin(),ord.end());
	/*for(auto i:ord){
		cout<<i<<":";
	}
	cout<<endl;*/
	for(int i=0;i<2*n;i++){
		pre[aa[i]].insert(i*2);
		pre[bb[i]].insert(i*2+1);
	}
	for(int j=0;j<8*n;j++){
		vis[j]=0;
	}
	for(auto j:ord){
		if(vis[j]==0){
			cur++;
			dfs2(j);
		}
	}
	int st=1;
	for(int i=0;i<8*n;i+=2){
		if(vis[i]==vis[i+1]){
			st=0;
		}

	}

	/*for(int i=0;i<8*n;i++){
		cout<<vis[i]<<",";
	}
	cout<<endl;*/
	if(st){

		for(int i=0;i<8*n;i+=2){
			if(vis[i]<vis[i+1]){
				//i is false
			}
			else{
				//i is true
				if(i%4==0){
					ans5[aa[i/4]]=i/4;
				}
				else{
					ans5[bb[i/4]]=i/4;
				}
			}
		}
		for(int i=0;i<2*n;i++){
			//cout<<ans5[i]<<",";
			if(i<n){
				adj3[i].pb(bb[ans5[i]]);
				coo[adj3[i].back()]++;
			}
			else{
				adj3[i].pb(aa[ans5[i]]);
				coo[adj3[i].back()]++;
			}
		}
		/*cout<<endl;
		for(int i=0;i<2*n;i++){
			cout<<i<<",,"<<adj3[i][0]<<endl;
		}*/

		queue<int> ss;
		for(int i=0;i<2*n;i++){
			if(coo[i]==0){
				ss.push(i);
			}
		}
		while(ss.size()){
			int no=ss.front();
			ss.pop();
			kk[no]=1;
			for(auto j:adj3[no]){
				coo[j]--;
				if(coo[j]==0){
					ss.push(j);
				}
			}

		}
		int su=0;
		int su2=0;
		for(int i=0;i<2*n;i++){
			if(kk[i]==1){
				if(i<n){
					su+=it[ans5[i]];
				}
				else{
					su2+=it[ans5[i]];
				}
			}
			//cout<<kk[i]<<".";
		}
		llo xx5=0;
		for(int i=0;i<2*n;i++){
			xx5+=it[i];
		}
		if(xx5==2*n){
			cout<<"YES"<<endl;
			return 0;
		}
		//cout<<endl;
		//cout<<su<<"<<"<<su2<<endl;
		vector<pair<llo,llo>> con;
		vector<llo> con2;
		for(int i=0;i<2*n;i++){
			if(kk[i]==0){
				pp.clear();
				dfs3(i);
				llo su3=0;
				llo su4=0;
				llo xx=0;
				for(auto j:pp){
					if(xx==0){
						su3+=j.b;
					}
					else{
						su4+=j.b;
					}
					xx^=1;
					//cout<<j.a<<"?"<<j.b<<endl;
				}
				int qq=min(su3,su4);
				su+=qq;
				su2+=qq;
				con.pb({su3-qq,su4-qq});
				con2.pb(max(su3-qq,su4-qq));
				//cout<<su3<<"?"<<su4<<endl;
			}
		}
		//cout<<su<<".."<<su2<<endl;
		int zz5=0;
		/*if(con.size()>30){
			while(true){
				continue;
			}
		}*/
	//	dp[0][su]=1;

		bitset<30001*20*2> dp2;
		dp2[su]=1;
		for(int i=0;i<con2.size();i++){
			dp2|=(dp2<<con2[i]);
		}
	/*	for(int i=1;i<=con.size();i++){
			for(int j=con[i-1].a;j<=20*2*n;j++){
				dp[i][j]|=dp[i-1][j-con[i-1].a];
			}
			for(int j=con[i-1].b;j<=20*2*n;j++){
				dp[i][j]|=dp[i-1][j-con[i-1].b];
			}

		}*/
		llo suu=0;
		for(int i=0;i<2*n;i++){
			suu+=it[i];
		}
		for(int i=0;i<=40*n;i++){
			if(dp2[i]){
				//cout<<i<<".."<<endl;
				if(abs(i-(suu-i))<=k){
					zz5=1;
					break;
				}
			}
		}
	/*	for(int i=0;i<(1<<con.size());i++){
			//cout<<i<<endl;
			int dd=su;
			int ee=su2;
			for(int j=0;j<con.size();j++){
				if((1<<j)&i){
					dd+=con[j].a;
					ee+=con[j].b;
				}
				else{
					dd+=con[j].b;
					ee+=con[j].a;
				}
			}
			//cout<<i<<"?"<<dd<<
			if(abs(dd-ee)<=k){

				zz5=1;
				break;
			}
		}*/
		if(zz5==0){
			cout<<"NO"<<endl;
			return 0;
		}


		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}











 
 
	return 0;
}
 

Compilation message (stderr)

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

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