| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94065 |
2019-01-15T15:36:48 Z |
updown1 |
Tug of War (BOI15_tug) |
C++17 |
|
163 ms |
10104 KB |
/*
nodes are spots (0-N-1:left, N - 2*N-1: right)
edges are people
weight of edge is strength
if there is only one edge in a node, remove and repeat
we are not left with cycles so all edges should have exactly two edges in it
find the possibility for each cycle
use bitset for quick dp
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, 2*N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=60000, INF=1000000000;
///500,000,000
int N, K, s1, s2, tot;
bool vis[MAXN];
vector<int> vals;
multiset<pair<int, int> > adj[MAXN];
multiset<pair<int, int> >::iterator it;
queue<int> emp;
bitset<10*MAXN+1> dp; /// 10*MAXN bc MAXN = 2*30,000
void go(int at, int diff, int put) {
if (vis[at]) {vals.pb(abs(diff)); return;}
vis[at] = true;
it = adj[at].begin();
int x = (*it).a, d = (*it).b;
if (put == 0) diff += d;
else diff -= d;
adj[x].erase(adj[x].find(mp(at, d)));
adj[at].erase(it);
go(x, diff, 1-put);
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> K;
ffi {
int a, b, d; cin >> a >> b >> d;
a--; b = b-1+N;
adj[a].insert(mp(b, d)); adj[b].insert(mp(a, d));
//w<< a s b<<e;
tot += d;
}
if (K%2 == 0 && tot%2 != 0) {
w<< "NO"<<e;
exit(0);
}
ffi if (adj[i].size() == 1) emp.push(i);
while (!emp.empty()) {
int x = emp.front(); emp.pop();
it = adj[x].begin();
if (x < N) s1 += (*it).b;
else s2 += (*it).b;
adj[(*it).a].erase(adj[(*it).a].find(mp(x, (*it).b)));
if (adj[(*it).a].size() == 1) emp.push((*it).a);
adj[x].erase(it);
}
ffi if (adj[i].size() != 2 && adj[i].size() != 0) {
w<< "NO"<<e;
exit(0);
}
ffi if (!vis[i] && adj[i].size() == 2) {
go(i, 0, 0);
}
tot = 0;
//for (int i: vals) w<< i<< " "; w<<e;
dp[s1-s2] = 1; /// check if this is correct
for (int i: vals) {
tot += i;
dp |= dp << (2*i);
}
For (i, 0, 10*MAXN+1) if (dp[i] == 1) {
//w<< i s tot<<e;
if (abs(tot-i) <= K) {
w<< "YES"<<e;
return 0;
}
}
w<< "NO"<<e;
}
Compilation message
tug.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 7 |
Correct |
5 ms |
3452 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 15 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 17 |
Correct |
0 ms |
3320 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 21 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 22 |
Runtime error |
7 ms |
6136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 7 |
Correct |
5 ms |
3452 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 15 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 17 |
Correct |
0 ms |
3320 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 21 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 22 |
Runtime error |
7 ms |
6136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
5468 KB |
Output is correct |
| 2 |
Runtime error |
18 ms |
10104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 7 |
Correct |
5 ms |
3452 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3448 KB |
Output is correct |
| 15 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 17 |
Correct |
0 ms |
3320 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3320 KB |
Output is correct |
| 21 |
Correct |
4 ms |
3192 KB |
Output is correct |
| 22 |
Runtime error |
7 ms |
6136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 23 |
Halted |
0 ms |
0 KB |
- |
