| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 94118 | 2019-01-16T09:53:53 Z | Kastanda | Tug of War (BOI15_tug) | C++11 | 72 ms | 5624 KB |
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 30004, MXN = N * 20;
int n, k, L[N], R[N], A[N], C[MXN];
bool M[N * 2];
set < int > Adj[N * 2];
bitset < MXN > B;
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n + n; i++)
{
scanf("%d%d%d", &L[i], &R[i], &A[i]);
R[i] += n;
Adj[L[i]].insert(i);
Adj[R[i]].insert(i);
}
for (int i = 1; i <= n + n; i++)
if (!Adj[i].size())
return !printf("NO");
queue < int > qu;
for (int i = 1; i <= n + n; i++)
if (Adj[i].size() == 1)
qu.push(i);
int L_sum = 0, R_sum = 0;
while (qu.size())
{
int v = qu.front(); qu.pop();
int id = * Adj[v].begin();
int u = L[id] ^ R[id] ^ v;
M[v] = 1;
if (v <= n)
L_sum += A[id];
else
R_sum += A[id];
if (M[u]) continue;
Adj[u].erase(id);
if (Adj[u].size() == 1)
qu.push(u);
//if (Adj[u].size() == 0)
//return !printf("NO");
}
int sum = 0;
memset(M, 0, sizeof(M));
for (int i = 1; i <= n + n; i++)
if (!M[i])
{
int v = i, p = 0, _sum = 0;
while (!M[v])
{
M[v] = 1;
Adj[v].erase(p);
int id = * Adj[v].begin();
int u = L[id] ^ R[id] ^ v;
_sum = -_sum + A[id];
p = id; v = u;
}
sum += abs(_sum);
C[abs(_sum)] ++;
}
for (int i = 1; i < MXN; i++)
if (C[i] > 2)
{
C[i + i] += (C[i] - 1) >> 1;
C[i] = (C[i] - 1 & 1) + 1;
}
B = 1;
for (int i = 1; i < MXN; i++)
for (int j = 1; j <= C[i]; j++)
B |= B << i;
sum += L_sum - R_sum;
for (int i = 0; i < MXN; i++)
if (B[i] && abs(sum - i - i) <= k)
return !printf("YES");
return !printf("NO");
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 3448 KB | Output is correct |
| 2 | Correct | 8 ms | 3448 KB | Output is correct |
| 3 | Correct | 7 ms | 3448 KB | Output is correct |
| 4 | Correct | 7 ms | 3448 KB | Output is correct |
| 5 | Correct | 8 ms | 3448 KB | Output is correct |
| 6 | Correct | 8 ms | 3448 KB | Output is correct |
| 7 | Correct | 7 ms | 3448 KB | Output is correct |
| 8 | Correct | 7 ms | 3452 KB | Output is correct |
| 9 | Correct | 7 ms | 3448 KB | Output is correct |
| 10 | Correct | 7 ms | 3448 KB | Output is correct |
| 11 | Correct | 6 ms | 3448 KB | Output is correct |
| 12 | Correct | 7 ms | 3496 KB | Output is correct |
| 13 | Correct | 7 ms | 3448 KB | Output is correct |
| 14 | Correct | 7 ms | 3448 KB | Output is correct |
| 15 | Correct | 7 ms | 3448 KB | Output is correct |
| 16 | Correct | 7 ms | 3448 KB | Output is correct |
| 17 | Correct | 7 ms | 3448 KB | Output is correct |
| 18 | Correct | 6 ms | 3444 KB | Output is correct |
| 19 | Correct | 7 ms | 3448 KB | Output is correct |
| 20 | Correct | 6 ms | 3448 KB | Output is correct |
| 21 | Correct | 3 ms | 3192 KB | Output is correct |
| 22 | Correct | 7 ms | 3448 KB | Output is correct |
| 23 | Incorrect | 6 ms | 3448 KB | Output isn't correct |
| 24 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 3448 KB | Output is correct |
| 2 | Correct | 8 ms | 3448 KB | Output is correct |
| 3 | Correct | 7 ms | 3448 KB | Output is correct |
| 4 | Correct | 7 ms | 3448 KB | Output is correct |
| 5 | Correct | 8 ms | 3448 KB | Output is correct |
| 6 | Correct | 8 ms | 3448 KB | Output is correct |
| 7 | Correct | 7 ms | 3448 KB | Output is correct |
| 8 | Correct | 7 ms | 3452 KB | Output is correct |
| 9 | Correct | 7 ms | 3448 KB | Output is correct |
| 10 | Correct | 7 ms | 3448 KB | Output is correct |
| 11 | Correct | 6 ms | 3448 KB | Output is correct |
| 12 | Correct | 7 ms | 3496 KB | Output is correct |
| 13 | Correct | 7 ms | 3448 KB | Output is correct |
| 14 | Correct | 7 ms | 3448 KB | Output is correct |
| 15 | Correct | 7 ms | 3448 KB | Output is correct |
| 16 | Correct | 7 ms | 3448 KB | Output is correct |
| 17 | Correct | 7 ms | 3448 KB | Output is correct |
| 18 | Correct | 6 ms | 3444 KB | Output is correct |
| 19 | Correct | 7 ms | 3448 KB | Output is correct |
| 20 | Correct | 6 ms | 3448 KB | Output is correct |
| 21 | Correct | 3 ms | 3192 KB | Output is correct |
| 22 | Correct | 7 ms | 3448 KB | Output is correct |
| 23 | Incorrect | 6 ms | 3448 KB | Output isn't correct |
| 24 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 5496 KB | Output is correct |
| 2 | Correct | 14 ms | 5240 KB | Output is correct |
| 3 | Correct | 21 ms | 5512 KB | Output is correct |
| 4 | Correct | 17 ms | 5332 KB | Output is correct |
| 5 | Correct | 19 ms | 5496 KB | Output is correct |
| 6 | Correct | 18 ms | 5240 KB | Output is correct |
| 7 | Correct | 21 ms | 5496 KB | Output is correct |
| 8 | Correct | 16 ms | 5240 KB | Output is correct |
| 9 | Correct | 20 ms | 5496 KB | Output is correct |
| 10 | Correct | 17 ms | 5240 KB | Output is correct |
| 11 | Correct | 21 ms | 5500 KB | Output is correct |
| 12 | Correct | 14 ms | 5240 KB | Output is correct |
| 13 | Correct | 21 ms | 5496 KB | Output is correct |
| 14 | Correct | 17 ms | 5496 KB | Output is correct |
| 15 | Correct | 14 ms | 5240 KB | Output is correct |
| 16 | Correct | 17 ms | 5496 KB | Output is correct |
| 17 | Correct | 14 ms | 5240 KB | Output is correct |
| 18 | Correct | 18 ms | 5496 KB | Output is correct |
| 19 | Correct | 72 ms | 5240 KB | Output is correct |
| 20 | Correct | 18 ms | 5496 KB | Output is correct |
| 21 | Correct | 15 ms | 5240 KB | Output is correct |
| 22 | Correct | 20 ms | 5624 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 3448 KB | Output is correct |
| 2 | Correct | 8 ms | 3448 KB | Output is correct |
| 3 | Correct | 7 ms | 3448 KB | Output is correct |
| 4 | Correct | 7 ms | 3448 KB | Output is correct |
| 5 | Correct | 8 ms | 3448 KB | Output is correct |
| 6 | Correct | 8 ms | 3448 KB | Output is correct |
| 7 | Correct | 7 ms | 3448 KB | Output is correct |
| 8 | Correct | 7 ms | 3452 KB | Output is correct |
| 9 | Correct | 7 ms | 3448 KB | Output is correct |
| 10 | Correct | 7 ms | 3448 KB | Output is correct |
| 11 | Correct | 6 ms | 3448 KB | Output is correct |
| 12 | Correct | 7 ms | 3496 KB | Output is correct |
| 13 | Correct | 7 ms | 3448 KB | Output is correct |
| 14 | Correct | 7 ms | 3448 KB | Output is correct |
| 15 | Correct | 7 ms | 3448 KB | Output is correct |
| 16 | Correct | 7 ms | 3448 KB | Output is correct |
| 17 | Correct | 7 ms | 3448 KB | Output is correct |
| 18 | Correct | 6 ms | 3444 KB | Output is correct |
| 19 | Correct | 7 ms | 3448 KB | Output is correct |
| 20 | Correct | 6 ms | 3448 KB | Output is correct |
| 21 | Correct | 3 ms | 3192 KB | Output is correct |
| 22 | Correct | 7 ms | 3448 KB | Output is correct |
| 23 | Incorrect | 6 ms | 3448 KB | Output isn't correct |
| 24 | Halted | 0 ms | 0 KB | - |