Submission #104619

#	Time	Username	Problem	Language	Result	Execution time	Memory
104619		alexpetrescu	Tug of War (BOI15_tug)	C++14	100 / 100	2295 ms	5368 KiB

tug

#include <cstdio>
#include <bitset>
#include <vector>
#include <cstdlib>
#include <algorithm>

//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout

#define MAXN 60009
#define MAXS 1170009

std::bitset < MAXS > d;
bool cuplat[MAXN], done[MAXN];
int gr[MAXN], D, q[MAXN], add[MAXN];
int n, l[MAXN], r[MAXN], s[MAXN];
std::vector < int > g[MAXN];

inline void go(int x) {
    while (x) {
        int a = l[x];
        if (cuplat[a])
            a = r[x];
        if (cuplat[a])
            exit(1);
        cuplat[a] = 1;
        done[x] = 1;
        if (a <= n)
            D -= s[x];
        else
            D += s[x];
        x = 0;
        for (auto &y : g[a])
            if (done[y] == 0)
                x = y;
    }
}

int main() {
    int k;
    fscanf(fin, "%d%d", &n, &k);

    for (int i = 1; i <= 2 * n; i++) {
        fscanf(fin, "%d%d%d", &l[i], &r[i], &s[i]);
        r[i] += n;
        g[l[i]].push_back(i);
        g[r[i]].push_back(i);
    }

    for (int i = 1; i <= 2 * n; i++)
        gr[i] = g[i].size();

    int st = 0, dr = 0;
    for (int i = 1; i <= 2 * n; i++)
        if (gr[i] <= 1)
            q[dr++] = i;

    int dif = 0;
    while (st < dr) {
        int x = q[st++];
        if (gr[x] == 0) {
            fprintf(fout, "NO");
            return 0;
        }
        cuplat[x] = 1;
        int nod = 0;
        for (auto &y : g[x])
            if (done[y] == 0)
                nod = y;
        if (nod == 0)
            exit(2);
        done[nod] = 1;
        int z = l[nod] ^ r[nod] ^ x;
        gr[z]--;
        if (gr[z] == 1)
            q[dr++] = z;
        if (x <= n)
            dif -= s[nod];
        else
            dif += s[nod];
    }

    for (int i = 1; i <= 2 * n; i++) {
        if (done[i] == 0) {
            D = 0;
            go(i);
            if (D < 0)
                D = -D;
            dif -= D;
            add[++add[0]] = 2 * D;
        }
    }

    int left = -k - dif, right = k - dif;
    if (right < 0)
        fprintf(fout, "NO");
    else if (left <= 0)
        fprintf(fout, "YES");
    else {
        std::sort(add + 1, add + add[0] + 1);
        for (int i = 1; i <= add[0]; i++)
            add[i] /= 2;
        left = (left + 1) / 2;
        right = right / 2;
        d[0] = 1;
        for (int i = 1; i <= add[0]; i++)
            d |= d << add[i];
        bool ans = 0;
        for (int i = left; i <= right; i++)
            ans |= d[i];
        if (ans)
            fprintf(fout, "YES");
        else
            fprintf(fout, "NO");
    }

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:42:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d%d", &n, &k);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~
tug.cpp:45:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d%d%d", &l[i], &r[i], &s[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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