# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
30931 | 2017-08-01T07:56:08 Z | Navick | Tug of War (BOI15_tug) | C++14 | 1346 ms | 8800 KB |
#include <bits/stdc++.h> #define F first #define S second #define pii pair<int, int> #define pb push_back using namespace std; typedef long long ll; typedef long double ld; const int N = 3e4 + 10, K = 30; int n, k, deg[2 * N], suml, sumr, sum, p[N]; vector<int> adj[4 * N]; bool mark[4 * N]; set<pii> s; pii vl[4 * N]; bitset<N * K> dp, foo; inline int pe(int i){ return 2 * n + i; } inline int rg(int i){ return i + n; } inline int lf(int i){ return i; } void dfs(int v, int c, int h = 0){ mark[v] = true; if(v>=2*n){ if(h % 4 == 1) vl[c].F += p[v]; else vl[c].S += p[v]; } for(auto u : adj[v]){ if(mark[u])continue; dfs(u, c, h + 1); } } int main(){ scanf("%d %d", &n, &k); for(int i=0; i<2*n; i++){ int l, r; scanf("%d %d", &l, &r); --l; --r; scanf("%d", &p[pe(i)]); sum += p[pe(i)]; adj[pe(i)].pb(lf(l)); adj[pe(i)].pb(rg(r)); adj[rg(r)].pb(pe(i)); adj[lf(l)].pb(pe(i)); } for(int i=0; i<2*n; i++){ deg[i] = (int)adj[i].size(); s.insert({deg[i], i}); } while(!s.empty()){ int v = (*s.begin()).S; s.erase(s.begin()); if(deg[v] == 0) return printf("NO\n"), 0; if(deg[v] == 1){ mark[v] = true; for(auto u : adj[v]){ if(mark[u])continue; mark[u] = true; for(auto x : adj[u]){ if(mark[x])continue; s.erase({deg[x], x}); deg[x]--; s.insert({deg[x], x}); } if(v < n) suml += p[u]; else sumr += p[u]; } } else break; } int cnt = 0; for(int i=0; i<2*n; i++){ if(mark[i])continue; dfs(i, cnt); cnt++; } dp[suml] = 1; for(int i=0; i<cnt; i++){ foo = dp; dp.reset(); dp |= foo << (vl[i].F); dp |= foo << (vl[i].S); } for(int i=(sum-k+1)/2; i<=(sum+k)/2; i++) if(dp[i]) return printf("YES\n"), 0; return printf("NO\n"), 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 6560 KB | Output is correct |
2 | Correct | 3 ms | 6564 KB | Output is correct |
3 | Correct | 3 ms | 6560 KB | Output is correct |
4 | Correct | 0 ms | 6556 KB | Output is correct |
5 | Correct | 3 ms | 6560 KB | Output is correct |
6 | Correct | 3 ms | 6564 KB | Output is correct |
7 | Correct | 0 ms | 6556 KB | Output is correct |
8 | Correct | 0 ms | 6560 KB | Output is correct |
9 | Correct | 0 ms | 6564 KB | Output is correct |
10 | Correct | 3 ms | 6564 KB | Output is correct |
11 | Correct | 3 ms | 6560 KB | Output is correct |
12 | Correct | 0 ms | 6564 KB | Output is correct |
13 | Correct | 3 ms | 6560 KB | Output is correct |
14 | Correct | 3 ms | 6560 KB | Output is correct |
15 | Correct | 3 ms | 6556 KB | Output is correct |
16 | Correct | 0 ms | 6564 KB | Output is correct |
17 | Correct | 0 ms | 6560 KB | Output is correct |
18 | Correct | 0 ms | 6560 KB | Output is correct |
19 | Correct | 3 ms | 6564 KB | Output is correct |
20 | Correct | 3 ms | 6556 KB | Output is correct |
21 | Correct | 0 ms | 6560 KB | Output is correct |
22 | Correct | 0 ms | 6560 KB | Output is correct |
23 | Correct | 0 ms | 6560 KB | Output is correct |
24 | Correct | 3 ms | 6560 KB | Output is correct |
25 | Correct | 3 ms | 6560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 6560 KB | Output is correct |
2 | Correct | 3 ms | 6564 KB | Output is correct |
3 | Correct | 3 ms | 6560 KB | Output is correct |
4 | Correct | 0 ms | 6556 KB | Output is correct |
5 | Correct | 3 ms | 6560 KB | Output is correct |
6 | Correct | 3 ms | 6564 KB | Output is correct |
7 | Correct | 0 ms | 6556 KB | Output is correct |
8 | Correct | 0 ms | 6560 KB | Output is correct |
9 | Correct | 0 ms | 6564 KB | Output is correct |
10 | Correct | 3 ms | 6564 KB | Output is correct |
11 | Correct | 3 ms | 6560 KB | Output is correct |
12 | Correct | 0 ms | 6564 KB | Output is correct |
13 | Correct | 3 ms | 6560 KB | Output is correct |
14 | Correct | 3 ms | 6560 KB | Output is correct |
15 | Correct | 3 ms | 6556 KB | Output is correct |
16 | Correct | 0 ms | 6564 KB | Output is correct |
17 | Correct | 0 ms | 6560 KB | Output is correct |
18 | Correct | 0 ms | 6560 KB | Output is correct |
19 | Correct | 3 ms | 6564 KB | Output is correct |
20 | Correct | 3 ms | 6556 KB | Output is correct |
21 | Correct | 0 ms | 6560 KB | Output is correct |
22 | Correct | 0 ms | 6560 KB | Output is correct |
23 | Correct | 0 ms | 6560 KB | Output is correct |
24 | Correct | 3 ms | 6560 KB | Output is correct |
25 | Correct | 3 ms | 6560 KB | Output is correct |
26 | Correct | 256 ms | 6956 KB | Output is correct |
27 | Correct | 46 ms | 6960 KB | Output is correct |
28 | Correct | 279 ms | 6956 KB | Output is correct |
29 | Correct | 56 ms | 6956 KB | Output is correct |
30 | Correct | 296 ms | 6956 KB | Output is correct |
31 | Correct | 39 ms | 6952 KB | Output is correct |
32 | Correct | 259 ms | 6952 KB | Output is correct |
33 | Correct | 43 ms | 6960 KB | Output is correct |
34 | Correct | 23 ms | 6968 KB | Output is correct |
35 | Correct | 46 ms | 6956 KB | Output is correct |
36 | Correct | 293 ms | 6960 KB | Output is correct |
37 | Correct | 36 ms | 6956 KB | Output is correct |
38 | Correct | 266 ms | 6960 KB | Output is correct |
39 | Correct | 39 ms | 6956 KB | Output is correct |
40 | Correct | 273 ms | 6956 KB | Output is correct |
41 | Correct | 36 ms | 6960 KB | Output is correct |
42 | Correct | 276 ms | 6956 KB | Output is correct |
43 | Correct | 43 ms | 6960 KB | Output is correct |
44 | Correct | 259 ms | 6956 KB | Output is correct |
45 | Correct | 53 ms | 6952 KB | Output is correct |
46 | Correct | 286 ms | 6956 KB | Output is correct |
47 | Correct | 6 ms | 6956 KB | Output is correct |
48 | Correct | 139 ms | 6960 KB | Output is correct |
49 | Correct | 146 ms | 6956 KB | Output is correct |
50 | Correct | 279 ms | 6960 KB | Output is correct |
51 | Correct | 276 ms | 6956 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1346 ms | 8800 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 6560 KB | Output is correct |
2 | Correct | 3 ms | 6564 KB | Output is correct |
3 | Correct | 3 ms | 6560 KB | Output is correct |
4 | Correct | 0 ms | 6556 KB | Output is correct |
5 | Correct | 3 ms | 6560 KB | Output is correct |
6 | Correct | 3 ms | 6564 KB | Output is correct |
7 | Correct | 0 ms | 6556 KB | Output is correct |
8 | Correct | 0 ms | 6560 KB | Output is correct |
9 | Correct | 0 ms | 6564 KB | Output is correct |
10 | Correct | 3 ms | 6564 KB | Output is correct |
11 | Correct | 3 ms | 6560 KB | Output is correct |
12 | Correct | 0 ms | 6564 KB | Output is correct |
13 | Correct | 3 ms | 6560 KB | Output is correct |
14 | Correct | 3 ms | 6560 KB | Output is correct |
15 | Correct | 3 ms | 6556 KB | Output is correct |
16 | Correct | 0 ms | 6564 KB | Output is correct |
17 | Correct | 0 ms | 6560 KB | Output is correct |
18 | Correct | 0 ms | 6560 KB | Output is correct |
19 | Correct | 3 ms | 6564 KB | Output is correct |
20 | Correct | 3 ms | 6556 KB | Output is correct |
21 | Correct | 0 ms | 6560 KB | Output is correct |
22 | Correct | 0 ms | 6560 KB | Output is correct |
23 | Correct | 0 ms | 6560 KB | Output is correct |
24 | Correct | 3 ms | 6560 KB | Output is correct |
25 | Correct | 3 ms | 6560 KB | Output is correct |
26 | Correct | 256 ms | 6956 KB | Output is correct |
27 | Correct | 46 ms | 6960 KB | Output is correct |
28 | Correct | 279 ms | 6956 KB | Output is correct |
29 | Correct | 56 ms | 6956 KB | Output is correct |
30 | Correct | 296 ms | 6956 KB | Output is correct |
31 | Correct | 39 ms | 6952 KB | Output is correct |
32 | Correct | 259 ms | 6952 KB | Output is correct |
33 | Correct | 43 ms | 6960 KB | Output is correct |
34 | Correct | 23 ms | 6968 KB | Output is correct |
35 | Correct | 46 ms | 6956 KB | Output is correct |
36 | Correct | 293 ms | 6960 KB | Output is correct |
37 | Correct | 36 ms | 6956 KB | Output is correct |
38 | Correct | 266 ms | 6960 KB | Output is correct |
39 | Correct | 39 ms | 6956 KB | Output is correct |
40 | Correct | 273 ms | 6956 KB | Output is correct |
41 | Correct | 36 ms | 6960 KB | Output is correct |
42 | Correct | 276 ms | 6956 KB | Output is correct |
43 | Correct | 43 ms | 6960 KB | Output is correct |
44 | Correct | 259 ms | 6956 KB | Output is correct |
45 | Correct | 53 ms | 6952 KB | Output is correct |
46 | Correct | 286 ms | 6956 KB | Output is correct |
47 | Correct | 6 ms | 6956 KB | Output is correct |
48 | Correct | 139 ms | 6960 KB | Output is correct |
49 | Correct | 146 ms | 6956 KB | Output is correct |
50 | Correct | 279 ms | 6960 KB | Output is correct |
51 | Correct | 276 ms | 6956 KB | Output is correct |
52 | Incorrect | 1346 ms | 8800 KB | Output isn't correct |
53 | Halted | 0 ms | 0 KB | - |