Submission #198461

#	Time	Username	Problem	Language	Result	Execution time	Memory
198461		dndhk	Tug of War (BOI15_tug)	C++14	100 / 100	2397 ms	5780 KiB

tug

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 60000;

typedef pair<int, int> pii;

int N, K;
bool fin = false;
int c[MAX_N+1];
vector<pii> gp[MAX_N+1];

bool chk[MAX_N+1];
bool vst[MAX_N+1];

int S;
vector<int> vt;
vector<pii> v;

bitset<MAX_N*20+1> bt;

bool dfs(int x){
	vst[x] = true;
	for(pii i : gp[x]){
		if(chk[i.second])	continue;
		chk[i.second] = true;
		if(vst[i.first]){
			int sum = 0;
			if(x>N) sum+=c[i.second];
			else sum-=c[i.second];
			while(!v.empty()){
				if(v.back().first>N){
					sum+=v.back().second;
				}else{
					sum-=v.back().second;
				}
				if(v.back().first==i.first){
					vt.pb((sum>0?sum:-sum));
					sum = 0;
				}
				v.pop_back();
			}
			S+=sum;
			return true;
		}else{
			v.pb({x, c[i.second]});
			if(dfs(i.first)){
				return true;
			}
		}
	}
	if(!v.empty()){
		if(x>N){
			S += v.back().second;
		}else{
			S -= v.back().second;
		}
		v.pop_back();
		return false;
	}
	fin = true;
	return true;
}

int main(){
	scanf("%d%d", &N, &K);
	//cout<<N<<" "<<K<<endl;
	for(int i=1; i<=N*2; i++){
		int l, r;
		scanf("%d%d%d", &l, &r, &c[i]);
		//cout<<l<<" "<<r<<endl;
		r+=N;
		gp[l].pb({r, i});
		gp[r].pb({l, i});
	}
	for(int i=1; i<=N*2; i++){
		if(!vst[i]){
			dfs(i);
			if(fin==true){
				printf("NO");
				return 0;
			}
		}
	}
	if(S<0)	S*=-1;
	int S2 = 0;
	for(int i : vt)	S2 += i;
	// for(int i : vt){
	// 	cout<<i<<endl;
	// }
	bt[0] = true;
	int s = (S2-K-S+1)/2, e = (S2-S+K)/2;
	if(S2-S+K<0){
		printf("NO");
		return 0;
	}
	//cout<<S<<" "<<S2<<" "<<K<<endl;
	s = max(s, 0);
	for(int i : vt){
		bt = (bt | (bt<<i));
	}
	for(int j=s; j<=e; j++){
		//cout<<j<<" "<<bt[j]<<endl;
		if(bt[j]){
			printf("YES");
			return 0;
		}
	}
	printf("NO");
	return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &l, &r, &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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