답안 #677211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677211	2023-01-02T14:58:29 Z	faribourz	Tug of War (BOI15_tug)	C++14	0 / 100	3000 ms	11312 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

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9740 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	6 ms	9684 KB	Output is correct
5	Correct	7 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	6 ms	9684 KB	Output is correct
9	Correct	5 ms	9612 KB	Output is correct
10	Correct	5 ms	9632 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	6 ms	9728 KB	Output is correct
13	Correct	5 ms	9720 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	9684 KB	Output is correct
17	Correct	6 ms	9684 KB	Output is correct
18	Correct	5 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	Incorrect	5 ms	9684 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9740 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	6 ms	9684 KB	Output is correct
5	Correct	7 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	6 ms	9684 KB	Output is correct
9	Correct	5 ms	9612 KB	Output is correct
10	Correct	5 ms	9632 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	6 ms	9728 KB	Output is correct
13	Correct	5 ms	9720 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	9684 KB	Output is correct
17	Correct	6 ms	9684 KB	Output is correct
18	Correct	5 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	Incorrect	5 ms	9684 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	11312 KB	Output is correct
2	Execution timed out	3068 ms	11184 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9740 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	6 ms	9684 KB	Output is correct
5	Correct	7 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	6 ms	9684 KB	Output is correct
9	Correct	5 ms	9612 KB	Output is correct
10	Correct	5 ms	9632 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	6 ms	9728 KB	Output is correct
13	Correct	5 ms	9720 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	9684 KB	Output is correct
17	Correct	6 ms	9684 KB	Output is correct
18	Correct	5 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	Incorrect	5 ms	9684 KB	Output isn't correct
22	Halted	0 ms	0 KB	-