# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24452 | 2017-06-08T08:28:35 Z | Bruteforceman | Tug of War (BOI15_tug) | C++11 | 19 ms | 5084 KB |
#include "bits/stdc++.h" using namespace std; bool del[2 * 30005]; int deg[2][30005]; vector <int> g[2][30005]; struct data { int l, r, s; data () {} data (int l, int r, int s) : l(l), r(r), s(s) {} } a[2 * 30005]; struct node { int i, side; node () {} node (int i, int side) : i(i), side(side) {} }; int main(int argc, char const *argv[]) { int n, k; scanf("%d %d", &n, &k); for(int i = 1; i <= n+n; i++) { int l, r, s; scanf("%d %d %d", &l, &r, &s); a[i] = data(l, r, s); g[0][l].push_back(i); g[1][r].push_back(i); ++deg[0][l]; ++deg[1][r]; } queue <node> Q; for(int i = 1; i <= n; i++) { // cout << i << " " << deg[0][i] << " " << deg[1][i] << endl; if(deg[0][i] == 1) Q.push(node(i, 0)); if(deg[1][i] == 1) Q.push(node(i, 1)); if(deg[0][i] == 0 || deg[1][i] == 0) { printf("NO\n"); exit(0); } } int sum[2]; sum[0] = sum[1] = 0; while(!Q.empty()) { node p = Q.front(); Q.pop(); for(auto i : g[p.side][p.i]) { if(del[i] == false) { // cout << "match " << p.side << " " << p.i << " with " << i << endl; sum[p.side] += a[i].s; del[i] = true; if(p.side == 0) { --deg[1][a[i].r]; if(deg[1][a[i].r] == 1) { Q.push(node(a[i].r, 1)); } if(deg[1][a[i].r] == 0) { printf("NO\n"); exit(0); } } else { --deg[0][a[i].l]; if(deg[0][a[i].l] == 1) { Q.push(node(a[i].l, 0)); } if(deg[0][a[i].l] == 0) { printf("NO\n"); exit(0); } } } } } printf("YES\n"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 4424 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 4424 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 5084 KB | Output is correct |
2 | Correct | 13 ms | 5084 KB | Output is correct |
3 | Correct | 6 ms | 5084 KB | Output is correct |
4 | Correct | 6 ms | 5084 KB | Output is correct |
5 | Correct | 13 ms | 5084 KB | Output is correct |
6 | Correct | 13 ms | 5084 KB | Output is correct |
7 | Correct | 6 ms | 5084 KB | Output is correct |
8 | Correct | 13 ms | 5084 KB | Output is correct |
9 | Correct | 13 ms | 5084 KB | Output is correct |
10 | Correct | 13 ms | 5084 KB | Output is correct |
11 | Correct | 13 ms | 5084 KB | Output is correct |
12 | Correct | 19 ms | 5084 KB | Output is correct |
13 | Correct | 13 ms | 5084 KB | Output is correct |
14 | Correct | 6 ms | 5084 KB | Output is correct |
15 | Correct | 9 ms | 5084 KB | Output is correct |
16 | Correct | 16 ms | 5084 KB | Output is correct |
17 | Correct | 9 ms | 5084 KB | Output is correct |
18 | Correct | 9 ms | 5084 KB | Output is correct |
19 | Correct | 13 ms | 5084 KB | Output is correct |
20 | Correct | 13 ms | 5084 KB | Output is correct |
21 | Correct | 13 ms | 4952 KB | Output is correct |
22 | Correct | 13 ms | 5084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 4424 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |