Submission #208601

#	Time	Username	Problem	Language	Result	Execution time	Memory
208601		dolphingarlic	Tug of War (BOI15_tug)	C++14	0 / 100	36 ms	11640 KiB

tug

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

multiset<pair<int, int>> graph[60001];
bool visited[60001], possible[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;
    graph[nxt].erase({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].erase(graph[i].begin());
        dfs(i);
        if (tot) items.push_back(abs(tot));
    }
    sm = accumulate(items.begin(), items.end(), 0);

    possible[0] = true;
    for (int i : items) for (int j = i; j <= sm; j++) {
        possible[j] |= possible[j - i];
        if (possible[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:22: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:25: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: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29