oj.uz

Submission #677212

# Submission time Handle Problem Language Result Execution time Memory
677212 2023-01-02T14:59:10 Z ajab_01 Strange Device (APIO19_strange_device) C++17
0 / 100
 2 ms 2680 KB 
#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[11];
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -