답안 #677208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677208	2023-01-02T14:55:09 Z	faribourz	Tug of War (BOI15_tug)	C++14	0 / 100	17 ms	11708 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){
	mark[v] = 1;
	if(v <= 2*n)
		guni.pb(v);
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	4 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	4 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	4 ms	9720 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	4 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	5 ms	9684 KB	Output is correct
15	Correct	5 ms	9700 KB	Output is correct
16	Correct	5 ms	9732 KB	Output is correct
17	Correct	5 ms	9732 KB	Output is correct
18	Correct	5 ms	9684 KB	Output is correct
19	Correct	5 ms	9708 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Incorrect	5 ms	9684 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	4 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	4 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	4 ms	9720 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	4 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	5 ms	9684 KB	Output is correct
15	Correct	5 ms	9700 KB	Output is correct
16	Correct	5 ms	9732 KB	Output is correct
17	Correct	5 ms	9732 KB	Output is correct
18	Correct	5 ms	9684 KB	Output is correct
19	Correct	5 ms	9708 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Incorrect	5 ms	9684 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	11348 KB	Output is correct
2	Correct	13 ms	11092 KB	Output is correct
3	Correct	15 ms	11604 KB	Output is correct
4	Correct	16 ms	11416 KB	Output is correct
5	Correct	15 ms	11604 KB	Output is correct
6	Correct	14 ms	11412 KB	Output is correct
7	Correct	17 ms	11576 KB	Output is correct
8	Correct	14 ms	11412 KB	Output is correct
9	Correct	14 ms	11540 KB	Output is correct
10	Correct	17 ms	11396 KB	Output is correct
11	Correct	14 ms	11560 KB	Output is correct
12	Correct	14 ms	11348 KB	Output is correct
13	Correct	14 ms	11604 KB	Output is correct
14	Correct	14 ms	11528 KB	Output is correct
15	Correct	14 ms	11340 KB	Output is correct
16	Correct	14 ms	11708 KB	Output is correct
17	Correct	14 ms	11376 KB	Output is correct
18	Correct	14 ms	11588 KB	Output is correct
19	Correct	17 ms	11668 KB	Output is correct
20	Correct	17 ms	11532 KB	Output is correct
21	Correct	13 ms	11352 KB	Output is correct
22	Incorrect	14 ms	11388 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	4 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	4 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	4 ms	9720 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	4 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	5 ms	9684 KB	Output is correct
15	Correct	5 ms	9700 KB	Output is correct
16	Correct	5 ms	9732 KB	Output is correct
17	Correct	5 ms	9732 KB	Output is correct
18	Correct	5 ms	9684 KB	Output is correct
19	Correct	5 ms	9708 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Incorrect	5 ms	9684 KB	Output isn't correct
23	Halted	0 ms	0 KB	-