Submission #208602

#	Time	Username	Problem	Language	Result	Execution time	Memory
208602		dolphingarlic	Tug of War (BOI15_tug)	C++14	71 / 100	130 ms	9900 KiB

tug

#include <bits/stdc++.h>
using namespace std;

multiset<pair<int, int>> graph[60001];
bool visited[60001], possible[2][600001];
int tot = 0, sm = 0;

void dfs(int node) {
    visited[node] = true;
    if (!graph[node].size()) return;
    int nxt, cost;
    tie(nxt, cost) = *graph[node].begin();

    tot += cost;
    if (!visited[nxt]) {
        graph[nxt].erase(graph[nxt].find({node, -cost}));
        graph[node].clear();
        dfs(nxt);
    }
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= 2 * n; i++) {
        int l, r, s;
        scanf("%d %d %d", &l, &r, &s);
        graph[l].insert({n + r, s});
        graph[n + r].insert({l, -s});
    }

    queue<int> q;
    for (int i = 1; i <= 2 * n; i++) {
        if (graph[i].size() == 1) q.push(i);
        if (graph[i].size() == 0) return printf("NO\n"), 0;
    }
    while (q.size()) {
        int curr = q.front();
        q.pop();
        if (graph[curr].size() == 0) return printf("NO\n"), 0;
        int nxt, cost;
        tie(nxt, cost) = *graph[curr].begin();
        tot += cost;

        graph[curr].clear();
        graph[nxt].erase(graph[nxt].find({curr, -cost}));
        if (graph[nxt].size() == 1) q.push(nxt);
    }

    vector<int> items;
    if (tot) items.push_back(abs(tot));
    for (int i = 1; i <= 2 * n; i++) if (!visited[i] && graph[i].size()) {
        tot = 0;
        graph[i].erase(graph[i].begin());
        dfs(i);
        if (tot) items.push_back(abs(tot));
    }
    sm = accumulate(items.begin(), items.end(), 0);

    if (n > 2000) {
        if (items.size() & 1) return printf("NO\n"), 0;
        else return printf("YES\n"), 0;
    }

    possible[1][0] = true;
    for (int i = 0; i < items.size(); i++) for (int j = 0; j <= sm; j++) {
        possible[i & 1][j] = possible[1 - (i & 1)][j];
        if (j >= items[i]) possible[i & 1][j] |= possible[1 - (i & 1)][j - items[i]];
        if (possible[i & 1][j] && abs(2 * j - sm) <= k) return printf("YES\n"), 0;
    }
    printf("NO\n");
    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < items.size(); i++) for (int j = 0; j <= sm; j++) {
                     ~~^~~~~~~~~~~~~~
tug.cpp:24: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:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &l, &r, &s);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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