Submission #677214

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
677214	2023-01-02T14:59:47 Z	faribourz	Tug of War (BOI15_tug)	C++14	0 / 100	30 ms	11372 KB

tug

// Only GOD
// believe in yourself
// nemidam del be in darde donya!
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define int ll
const int N = 4e5+100;

vector<int> G[N];
int s[N];
vector<int> greedy;
bool mark[N];
vector<int> guni;
int n, k;
void DFS(int v){
	if(v <= 2*n)
		guni.pb(v), mark[v] = 1;
	for(int u : G[v]){
		if(!mark[u])
			DFS(u);
	}
}
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= 2*n; i++){
		int v, u;
		cin >> v >> u;
		G[i].pb(v+2*n);G[v+2*n].pb(i);
		G[i].pb(u+3*n);G[u+3*n].pb(i);
		cin >> s[i];
	}
	for(int i = 2*n+1; i <= 4*n; i++){
		if(sz(G[i]) > 2)
			KILL("NO");
	}
	for(int i =1; i <= 2*n; i++){
		if(!mark[i]){
			guni.clear();
			DFS(i);
			int res =0 ;
			for(int j =0 ; j < sz(guni);j++){
				if(j & 1){
					res += s[guni[j]];
				}
				else{
					res -= s[guni[j]];
				}
			}
			greedy.pb(abs(res));
		}
	}
	//for(int u : greedy)
	//	cout << u << ' ' ;
	int n = sz(greedy);
	for(int mask = 0; mask < (1<<n); mask++){
		int res =0 ;
		for(int i = 0; i < n; i++){
			if(bit(mask, i)){
				res -= greedy[i];
			}
			else
				res += greedy[i];
		}
		if(abs(res)<= k)
			KILL("YES");
	}
	KILL("NO");
}

Subtask #1

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9732 KB	Output is correct
2	Correct	6 ms	9684 KB	Output is correct
3	Correct	5 ms	9668 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	5 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9736 KB	Output is correct
12	Correct	5 ms	9652 KB	Output is correct
13	Correct	5 ms	9684 KB	Output is correct
14	Correct	5 ms	9684 KB	Output is correct
15	Correct	5 ms	9684 KB	Output is correct
16	Correct	5 ms	9732 KB	Output is correct
17	Correct	5 ms	9728 KB	Output is correct
18	Correct	7 ms	9684 KB	Output is correct
19	Correct	6 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9732 KB	Output is correct
22	Incorrect	5 ms	9712 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9732 KB	Output is correct
2	Correct	6 ms	9684 KB	Output is correct
3	Correct	5 ms	9668 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	5 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9736 KB	Output is correct
12	Correct	5 ms	9652 KB	Output is correct
13	Correct	5 ms	9684 KB	Output is correct
14	Correct	5 ms	9684 KB	Output is correct
15	Correct	5 ms	9684 KB	Output is correct
16	Correct	5 ms	9732 KB	Output is correct
17	Correct	5 ms	9728 KB	Output is correct
18	Correct	7 ms	9684 KB	Output is correct
19	Correct	6 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9732 KB	Output is correct
22	Incorrect	5 ms	9712 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	11268 KB	Output is correct
2	Correct	13 ms	11220 KB	Output is correct
3	Correct	14 ms	11344 KB	Output is correct
4	Correct	14 ms	11216 KB	Output is correct
5	Correct	14 ms	11348 KB	Output is correct
6	Correct	15 ms	11136 KB	Output is correct
7	Correct	14 ms	11348 KB	Output is correct
8	Correct	13 ms	11092 KB	Output is correct
9	Correct	30 ms	11348 KB	Output is correct
10	Correct	13 ms	11092 KB	Output is correct
11	Correct	14 ms	11348 KB	Output is correct
12	Correct	14 ms	11220 KB	Output is correct
13	Correct	13 ms	11348 KB	Output is correct
14	Correct	13 ms	11348 KB	Output is correct
15	Correct	13 ms	11180 KB	Output is correct
16	Correct	13 ms	11284 KB	Output is correct
17	Correct	14 ms	11212 KB	Output is correct
18	Correct	15 ms	11324 KB	Output is correct
19	Correct	19 ms	11092 KB	Output is correct
20	Correct	14 ms	11372 KB	Output is correct
21	Correct	13 ms	11092 KB	Output is correct
22	Incorrect	14 ms	11220 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9732 KB	Output is correct
2	Correct	6 ms	9684 KB	Output is correct
3	Correct	5 ms	9668 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	5 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9736 KB	Output is correct
12	Correct	5 ms	9652 KB	Output is correct
13	Correct	5 ms	9684 KB	Output is correct
14	Correct	5 ms	9684 KB	Output is correct
15	Correct	5 ms	9684 KB	Output is correct
16	Correct	5 ms	9732 KB	Output is correct
17	Correct	5 ms	9728 KB	Output is correct
18	Correct	7 ms	9684 KB	Output is correct
19	Correct	6 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9732 KB	Output is correct
22	Incorrect	5 ms	9712 KB	Output isn't correct
23	Halted	0 ms	0 KB	-