| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 677209 |
2023-01-02T14:55:30 Z |
faribourz |
Tug of War (BOI15_tug) |
C++14 |
|
3000 ms |
11292 KB |
// 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 =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");
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9736 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
6 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 |
9736 KB |
Output is correct |
| 10 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 11 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 12 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 13 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 14 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 15 |
Correct |
5 ms |
9732 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 17 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 18 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 19 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 20 |
Correct |
5 ms |
9660 KB |
Output is correct |
| 21 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9736 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
6 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 |
9736 KB |
Output is correct |
| 10 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 11 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 12 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 13 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 14 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 15 |
Correct |
5 ms |
9732 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 17 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 18 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 19 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 20 |
Correct |
5 ms |
9660 KB |
Output is correct |
| 21 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
11292 KB |
Output is correct |
| 2 |
Execution timed out |
3093 ms |
11220 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9736 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
6 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 |
9736 KB |
Output is correct |
| 10 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 11 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 12 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 13 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 14 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 15 |
Correct |
5 ms |
9732 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 17 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 18 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 19 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 20 |
Correct |
5 ms |
9660 KB |
Output is correct |
| 21 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
