| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 559385 |
2022-05-09T17:08:30 Z |
Olympia |
Tug of War (BOI15_tug) |
C++17 |
|
53 ms |
3700 KB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > > adj;
vector<bool> hasVisited;
int ans = 0;
void dfs (int curNode, int prevNode) {
if (hasVisited[curNode]) {
return;
}
hasVisited[curNode] = true;
for (pair<int,int> p: adj[curNode]) {
if (p.first != prevNode) {
ans += p.second;
dfs (p.first, curNode);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
adj.resize(2 * n);
hasVisited.assign(2 * n, false);
map<pair<int,int>,vector<int> > myMap;
for (int i = 0; i < 2 * n; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
v += n;
myMap[make_pair(u, v)].push_back(w);
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, -w));
}
vector<int> tot;
for (int i = 0; i < n; i++) {
if (!hasVisited[i]) {
ans = 0;
if (adj[i].size() != 2) {
cout << "NO\n";
exit(0);
}
//cout << adj[i].size() << '\n';
//assert(adj[i].size() == 2);
dfs (i, adj[i].back().first);
tot.push_back(abs(ans));
}
}
for (auto& p: myMap) {
if (p.second.size() <= 1) {
continue;
}
int a = 0;
for (int j = 0; j < p.second.size(); j++) {
if (j % 2) a += p.second[j];
else a -= p.second[j];
}
tot.push_back(abs(a));
}
bitset<60000> bs;
bs.set(30000);
for (int j: tot) {
bs = (bs >> j) | (bs << j);
}
for (int i = 0; i <= k; i++) {
if (bs[30000 + i]) {
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
}
Compilation message
tug.cpp: In function 'int main()':
tug.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int j = 0; j < p.second.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
340 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
340 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
2656 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3640 KB |
Output is correct |
| 3 |
Correct |
45 ms |
2672 KB |
Output is correct |
| 4 |
Correct |
18 ms |
3700 KB |
Output is correct |
| 5 |
Correct |
53 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
15 ms |
3668 KB |
Output is correct |
| 7 |
Correct |
49 ms |
2680 KB |
Output is correct |
| 8 |
Correct |
13 ms |
3592 KB |
Output is correct |
| 9 |
Correct |
43 ms |
2748 KB |
Output is correct |
| 10 |
Correct |
13 ms |
3668 KB |
Output is correct |
| 11 |
Correct |
44 ms |
2744 KB |
Output is correct |
| 12 |
Correct |
14 ms |
3668 KB |
Output is correct |
| 13 |
Correct |
44 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
51 ms |
2756 KB |
Output is correct |
| 15 |
Correct |
16 ms |
3668 KB |
Output is correct |
| 16 |
Correct |
48 ms |
2684 KB |
Output is correct |
| 17 |
Correct |
13 ms |
3592 KB |
Output is correct |
| 18 |
Correct |
51 ms |
2696 KB |
Output is correct |
| 19 |
Correct |
12 ms |
3668 KB |
Output is correct |
| 20 |
Correct |
45 ms |
2744 KB |
Output is correct |
| 21 |
Correct |
13 ms |
3548 KB |
Output is correct |
| 22 |
Incorrect |
12 ms |
3116 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
0 ms |
340 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
