Submission #94118

#	Time	Username	Problem	Language	Result	Execution time	Memory
94118		Kastanda	Tug of War (BOI15_tug)	C++11	23 / 100	72 ms	5624 KiB

tug

#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 (stderr)

tug.cpp: In function 'int main()':
tug.cpp:71:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             C[i] = (C[i] - 1 & 1) + 1;
                     ~~~~~^~~
tug.cpp:11: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:14: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: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29