oj.uz

Submission #30936

# Submission time Handle Problem Language Result Execution time Memory
30936 2017-08-01T09:14:58 Z Navick Tug of War (BOI15_tug) C++14
0 / 100
 56 ms 13792 KB 
#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] = true;
	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++;
	
	}
	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

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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11712 KB Output is correct
2 Correct 0 ms 11720 KB Output is correct
3 Correct 0 ms 11712 KB Output is correct
4 Correct 0 ms 11716 KB Output is correct
5 Correct 3 ms 11720 KB Output is correct
6 Correct 3 ms 11720 KB Output is correct
7 Correct 0 ms 11712 KB Output is correct
8 Correct 3 ms 11720 KB Output is correct
9 Correct 0 ms 11720 KB Output is correct
10 Correct 3 ms 11720 KB Output is correct
11 Correct 0 ms 11712 KB Output is correct
12 Correct 3 ms 11716 KB Output is correct
13 Correct 3 ms 11712 KB Output is correct
14 Correct 3 ms 11716 KB Output is correct
15 Correct 0 ms 11712 KB Output is correct
16 Correct 3 ms 11712 KB Output is correct
17 Correct 0 ms 11712 KB Output is correct
18 Correct 3 ms 11716 KB Output is correct
19 Correct 0 ms 11716 KB Output is correct
20 Correct 0 ms 11716 KB Output is correct
21 Correct 0 ms 11548 KB Output is correct
22 Incorrect 3 ms 11716 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11712 KB Output is correct
2 Correct 0 ms 11720 KB Output is correct
3 Correct 0 ms 11712 KB Output is correct
4 Correct 0 ms 11716 KB Output is correct
5 Correct 3 ms 11720 KB Output is correct
6 Correct 3 ms 11720 KB Output is correct
7 Correct 0 ms 11712 KB Output is correct
8 Correct 3 ms 11720 KB Output is correct
9 Correct 0 ms 11720 KB Output is correct
10 Correct 3 ms 11720 KB Output is correct
11 Correct 0 ms 11712 KB Output is correct
12 Correct 3 ms 11716 KB Output is correct
13 Correct 3 ms 11712 KB Output is correct
14 Correct 3 ms 11716 KB Output is correct
15 Correct 0 ms 11712 KB Output is correct
16 Correct 3 ms 11712 KB Output is correct
17 Correct 0 ms 11712 KB Output is correct
18 Correct 3 ms 11716 KB Output is correct
19 Correct 0 ms 11716 KB Output is correct
20 Correct 0 ms 11716 KB Output is correct
21 Correct 0 ms 11548 KB Output is correct
22 Incorrect 3 ms 11716 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13792 KB Output is correct
2 Correct 19 ms 13792 KB Output is correct
3 Correct 19 ms 13792 KB Output is correct
4 Correct 13 ms 13792 KB Output is correct
5 Correct 29 ms 13792 KB Output is correct
6 Correct 33 ms 13792 KB Output is correct
7 Correct 26 ms 13792 KB Output is correct
8 Correct 26 ms 13792 KB Output is correct
9 Correct 19 ms 13792 KB Output is correct
10 Correct 26 ms 13792 KB Output is correct
11 Correct 36 ms 13792 KB Output is correct
12 Correct 16 ms 13792 KB Output is correct
13 Correct 19 ms 13792 KB Output is correct
14 Correct 29 ms 13792 KB Output is correct
15 Correct 23 ms 13792 KB Output is correct
16 Correct 13 ms 13792 KB Output is correct
17 Correct 23 ms 13792 KB Output is correct
18 Correct 19 ms 13792 KB Output is correct
19 Correct 19 ms 13792 KB Output is correct
20 Correct 26 ms 13792 KB Output is correct
21 Correct 26 ms 13660 KB Output is correct
22 Incorrect 56 ms 13792 KB Output isn't correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11712 KB Output is correct
2 Correct 0 ms 11720 KB Output is correct
3 Correct 0 ms 11712 KB Output is correct
4 Correct 0 ms 11716 KB Output is correct
5 Correct 3 ms 11720 KB Output is correct
6 Correct 3 ms 11720 KB Output is correct
7 Correct 0 ms 11712 KB Output is correct
8 Correct 3 ms 11720 KB Output is correct
9 Correct 0 ms 11720 KB Output is correct
10 Correct 3 ms 11720 KB Output is correct
11 Correct 0 ms 11712 KB Output is correct
12 Correct 3 ms 11716 KB Output is correct
13 Correct 3 ms 11712 KB Output is correct
14 Correct 3 ms 11716 KB Output is correct
15 Correct 0 ms 11712 KB Output is correct
16 Correct 3 ms 11712 KB Output is correct
17 Correct 0 ms 11712 KB Output is correct
18 Correct 3 ms 11716 KB Output is correct
19 Correct 0 ms 11716 KB Output is correct
20 Correct 0 ms 11716 KB Output is correct
21 Correct 0 ms 11548 KB Output is correct
22 Incorrect 3 ms 11716 KB Output isn't correct
23 Halted 0 ms 0 KB -