Submission #30933

#	Time	Username	Problem	Language	Result	Execution time	Memory
30933		Navick	Tug of War (BOI15_tug)	C++14	71 / 100	296 ms	8940 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 = 30;

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

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;
	}

	if(n > 2000)return printf("YES\n"), 0;

	int cnt = 0;

	for(int i=0; i<2*n; i++){
		if(mark[i])continue;
		dfs(i, cnt);
		cnt++;
	}

	dp[suml] = 1;
	for(int i=0; i<cnt; i++){
		foo = dp;
		dp.reset();
		dp |= foo << (vl[i].F);
		dp |= foo << (vl[i].S);
	}

	for(int i=(sum-k+1)/2; i<=(sum+k)/2; i++)
		if(dp[i])
			return printf("YES\n"), 0;
	return printf("NO\n"), 0;
	
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:48: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:50: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:53: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: 0 / 29