Submission #30937

#	Time	Username	Problem	Language	Result	Execution time	Memory
30937		Navick	Tug of War (BOI15_tug)	C++14	100 / 100	209 ms	18320 KiB

tug

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3e4 + 10, K = 20;

int n, k, deg[2 * N], suml, sumr, sum, p[4 * N];
vector<int> adj[4 * N];
bool mark[4 * N];
set<pii> s;
pii vl[4 * N];
bitset<2 * N * K> dp;
int d[N], num[N * K], kol[N * K];

void solve(int m){
	for(int i=0; i<m; i++)
		num[d[i]]++;// cout << d[i] << " KI F" << endl;
	
	int sz = 0;
	for(int i=1; i<N*K; i++){
		if(num[i] == 0)continue;
		int pw = 1;
		while(pw*2 <= num[i]){
			kol[sz++] = pw * i;
			pw *= 2;
		}
		pw --;
		kol[sz++] = i *(num[i] - pw);
	}

	dp[0] = 1;
	for(int i=0; i<sz; i++)
		dp |= dp << kol[i];

}


inline int pe(int i){
	return 2 * n + i;
}

inline int rg(int i){
	return i + n;
}

inline int lf(int i){
	return i;
}

void dfs(int v, int c, int h = 0){
	mark[v] = true;
	if(v>=2*n){
		if(h % 4 == 1)
			vl[c].F += p[v];
		else
			vl[c].S += p[v];
	}
	for(auto u : adj[v]){
		if(mark[u])continue;
		dfs(u, c, h + 1);
	}
}

int main(){
	scanf("%d %d", &n, &k);
	for(int i=0; i<2*n; i++){
		int l, r; scanf("%d %d", &l, &r);
		--l; --r;

		scanf("%d", &p[pe(i)]); sum += p[pe(i)];

		adj[pe(i)].pb(lf(l));
		adj[pe(i)].pb(rg(r));
		adj[rg(r)].pb(pe(i));
		adj[lf(l)].pb(pe(i));
	}

	for(int i=0; i<2*n; i++){
		deg[i] = (int)adj[i].size();
		s.insert({deg[i], i});
	}

	while(!s.empty()){
		int v = (*s.begin()).S;
		s.erase(s.begin());

		if(deg[v] <= 0)
			return printf("NO\n"), 0;

		if(deg[v] == 1){
			mark[v] = true;
			for(auto u : adj[v]){
				if(mark[u])continue;
				mark[u] = true;
				for(auto x : adj[u]){
					if(mark[x])continue;
					s.erase({deg[x], x});
					deg[x]--;
					s.insert({deg[x], x});
				}
				if(v < n)
					suml += p[u];
				else sumr += p[u];
			}
		}
		else break;
	}

	int cnt = 0, mn = 0;

	for(int i=0; i<2*n; i++){
		if(mark[i])continue;
		dfs(i, cnt);
		if(vl[cnt].F > vl[cnt].S)
			swap(vl[cnt].F, vl[cnt].S);
		mn += vl[cnt].F;
		d[cnt] = vl[cnt].S - vl[cnt].F;
		cnt++;
	
	}

	mn += suml;
	solve(cnt);
	
	for(int i=0; i<N*K - mn; i++){
		if(i + mn >= (sum-k+1)/2 && i+mn <= (sum+k)/2)
			if(dp[i])return printf("YES\n"), 0;
	}
	return printf("NO\n"), 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:72:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
                        ^
tug.cpp:74:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int l, r; scanf("%d %d", &l, &r);
                                   ^
tug.cpp:77:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[pe(i)]); sum += p[pe(i)];
                         ^

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