답안 #677216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677216	2023-01-02T15:02:34 Z	ajab_01	Tug of War (BOI15_tug)	C++17	41 / 100	49 ms	4452 KB

tug

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N];
int l[N] , r[N] , p[N] , cnt[2] , n , k;
bool mark[N] , ch , flg = 1;

void dfs(int ver , int sit){
	mark[ver] = 1;
	cnt[sit]++;
	for(int i : g[ver]){
		if(mark[i]) continue;
		dfs(i , sit ^ 1);
	}
}

bool check(int mask){
	bool vis[21];
	memset(vis , 0 , sizeof(vis));
	int sum1 = 0 , sum2 = 0;
	for(int i = 0 ; i < 2 * n ; i++){
		if(mask & (1 << i)){
			if(vis[r[i]])
				return 0;
			vis[r[i]] = 1;
			sum1 += p[i];
		}
		else{
			if(vis[l[i]])
				return 0;
			vis[l[i]] = 1;
			sum2 += p[i];
		}
	}

	return abs(sum1 - sum2) <= k;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	if(n <= 10){
		for(int i = 0 ; i < 2 * n ; i++){
			cin >> l[i] >> r[i] >> p[i];
			r[i] += n;
		}

		for(int mask = 0 ; mask < (1 << 2 * n) ; mask++)
			if(check(mask))
				ch = 1;

		if(ch)
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
		return 0;
	}

	for(int i = 1 ; i <= 2 * n ; i++){
		cin >> l[i] >> r[i] >> p[i];
		g[i].push_back(l[i] + 2 * n);
		g[l[i] + 2 * n].push_back(i);
		g[i].push_back(r[i] + 3 * n);
		g[r[i] + 3 * n].push_back(i);
	}

	for(int i = 1 ; i <= 4 * n ; i++){
		if(!mark[i]){
			cnt[0] = cnt[1] = 0;
			dfs(i , (i > 2 * n ? 1 : 0));
			if(cnt[0] != cnt[1]) flg = 0;
		}
	}

	if(flg)
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';
	return 0;
}

Subtask #1

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	2644 KB	Output is correct
2	Correct	29 ms	2664 KB	Output is correct
3	Correct	30 ms	2668 KB	Output is correct
4	Correct	47 ms	2668 KB	Output is correct
5	Correct	49 ms	2668 KB	Output is correct
6	Correct	20 ms	2688 KB	Output is correct
7	Correct	35 ms	2644 KB	Output is correct
8	Correct	35 ms	2644 KB	Output is correct
9	Correct	31 ms	2644 KB	Output is correct
10	Correct	29 ms	2668 KB	Output is correct
11	Correct	39 ms	2644 KB	Output is correct
12	Correct	28 ms	2692 KB	Output is correct
13	Correct	32 ms	2764 KB	Output is correct
14	Correct	20 ms	2668 KB	Output is correct
15	Correct	38 ms	2644 KB	Output is correct
16	Correct	34 ms	2684 KB	Output is correct
17	Correct	28 ms	2684 KB	Output is correct
18	Correct	37 ms	2644 KB	Output is correct
19	Correct	37 ms	2644 KB	Output is correct
20	Correct	34 ms	2644 KB	Output is correct
21	Correct	19 ms	2684 KB	Output is correct
22	Correct	28 ms	2684 KB	Output is correct
23	Correct	26 ms	2644 KB	Output is correct
24	Correct	40 ms	2688 KB	Output is correct
25	Correct	34 ms	2680 KB	Output is correct

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	2644 KB	Output is correct
2	Correct	29 ms	2664 KB	Output is correct
3	Correct	30 ms	2668 KB	Output is correct
4	Correct	47 ms	2668 KB	Output is correct
5	Correct	49 ms	2668 KB	Output is correct
6	Correct	20 ms	2688 KB	Output is correct
7	Correct	35 ms	2644 KB	Output is correct
8	Correct	35 ms	2644 KB	Output is correct
9	Correct	31 ms	2644 KB	Output is correct
10	Correct	29 ms	2668 KB	Output is correct
11	Correct	39 ms	2644 KB	Output is correct
12	Correct	28 ms	2692 KB	Output is correct
13	Correct	32 ms	2764 KB	Output is correct
14	Correct	20 ms	2668 KB	Output is correct
15	Correct	38 ms	2644 KB	Output is correct
16	Correct	34 ms	2684 KB	Output is correct
17	Correct	28 ms	2684 KB	Output is correct
18	Correct	37 ms	2644 KB	Output is correct
19	Correct	37 ms	2644 KB	Output is correct
20	Correct	34 ms	2644 KB	Output is correct
21	Correct	19 ms	2684 KB	Output is correct
22	Correct	28 ms	2684 KB	Output is correct
23	Correct	26 ms	2644 KB	Output is correct
24	Correct	40 ms	2688 KB	Output is correct
25	Correct	34 ms	2680 KB	Output is correct
26	Correct	4 ms	2900 KB	Output is correct
27	Incorrect	3 ms	2900 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #3

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	4180 KB	Output is correct
2	Correct	11 ms	4124 KB	Output is correct
3	Correct	10 ms	4180 KB	Output is correct
4	Correct	11 ms	4156 KB	Output is correct
5	Correct	11 ms	4180 KB	Output is correct
6	Correct	14 ms	4120 KB	Output is correct
7	Correct	10 ms	4180 KB	Output is correct
8	Correct	10 ms	4180 KB	Output is correct
9	Correct	10 ms	4136 KB	Output is correct
10	Correct	12 ms	4180 KB	Output is correct
11	Correct	12 ms	4196 KB	Output is correct
12	Correct	12 ms	4180 KB	Output is correct
13	Correct	10 ms	4124 KB	Output is correct
14	Correct	9 ms	4180 KB	Output is correct
15	Correct	11 ms	4180 KB	Output is correct
16	Correct	9 ms	4180 KB	Output is correct
17	Correct	10 ms	4124 KB	Output is correct
18	Correct	13 ms	4132 KB	Output is correct
19	Correct	11 ms	4136 KB	Output is correct
20	Correct	10 ms	4180 KB	Output is correct
21	Correct	10 ms	4452 KB	Output is correct
22	Correct	10 ms	4216 KB	Output is correct

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	2644 KB	Output is correct
2	Correct	29 ms	2664 KB	Output is correct
3	Correct	30 ms	2668 KB	Output is correct
4	Correct	47 ms	2668 KB	Output is correct
5	Correct	49 ms	2668 KB	Output is correct
6	Correct	20 ms	2688 KB	Output is correct
7	Correct	35 ms	2644 KB	Output is correct
8	Correct	35 ms	2644 KB	Output is correct
9	Correct	31 ms	2644 KB	Output is correct
10	Correct	29 ms	2668 KB	Output is correct
11	Correct	39 ms	2644 KB	Output is correct
12	Correct	28 ms	2692 KB	Output is correct
13	Correct	32 ms	2764 KB	Output is correct
14	Correct	20 ms	2668 KB	Output is correct
15	Correct	38 ms	2644 KB	Output is correct
16	Correct	34 ms	2684 KB	Output is correct
17	Correct	28 ms	2684 KB	Output is correct
18	Correct	37 ms	2644 KB	Output is correct
19	Correct	37 ms	2644 KB	Output is correct
20	Correct	34 ms	2644 KB	Output is correct
21	Correct	19 ms	2684 KB	Output is correct
22	Correct	28 ms	2684 KB	Output is correct
23	Correct	26 ms	2644 KB	Output is correct
24	Correct	40 ms	2688 KB	Output is correct
25	Correct	34 ms	2680 KB	Output is correct
26	Correct	4 ms	2900 KB	Output is correct
27	Incorrect	3 ms	2900 KB	Output isn't correct
28	Halted	0 ms	0 KB	-