Submission #94122

#	Time	Username	Problem	Language	Result	Execution time	Memory
94122		Kastanda	Tug of War (BOI15_tug)	C++11	100 / 100	156 ms	13944 KiB

tug

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#define pb push_back
using namespace std;
const int N = 60004, 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 ((int)Adj[i].size() == 1)
            qu.push(i);

    int sum = 0;
    while (qu.size())
    {
        int v = qu.front(); qu.pop();
        assert((int)Adj[v].size() == 1);
        int id = * Adj[v].begin();
      	Adj[v].erase(Adj[v].begin());
        int u = L[id] ^ R[id] ^ v;
        M[v] = 1;

        if (v <= n)
            sum += A[id];
        else
            sum -= A[id];

        if (M[u]) return !printf("NO");
        Adj[u].erase(id);
        if ((int)Adj[u].size() == 1)
            qu.push(u);
        if (Adj[u].size() == 0)
            return !printf("NO");
    }

    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;

    for (int i = 0; i < MXN; i++)
        if (B[i] && abs(sum - i - i) <= k)
            return !printf("YES");
    return !printf("NO");
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:73:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             C[i] = (C[i] - 1 & 1) + 1;
                     ~~~~~^~~
tug.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &L[i], &R[i], &A[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29