Submission #404477

#	Time	Username	Problem	Language	Result	Execution time	Memory
404477		fvogel499	Tug of War (BOI15_tug)	C++14	71 / 100	3071 ms	12980 KiB

tug

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cassert>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define ll long long
#define rint int32_t

const int siz = 6000000;

bitset<siz> bit;

// ifstream cin("tug.in");
// ofstream cout("tug.out");

struct Edge {
    Edge(int lNA, int lNB, int lStrength) {
        nA = lNA;
        nB = lNB;
        strength = lStrength;
    }
    int nA, nB, strength;
};

rint main() {
    int n, tolerance;
    cin >> n >> tolerance;

    set<Edge*> graph [2*n];
    for (int i = 0; i < 2*n; i++) {
        int l, r, ls;
        cin >> l >> r >> ls;
        l--;
        r--;
        r += n;
        Edge* e = new Edge(l, r, ls);
        graph[l].insert(e);
        graph[r].insert(e);
    }

    int desequilibrium = 0;
    bool proc [2*n];
    for (int i = 0; i < 2*n; i++) proc[i] = false;
    queue<int> q;
    for (int i = 0; i < 2*n; i++) {
        if (graph[i].size() == 1) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int curNode = q.front();
        q.pop();
        if (proc[curNode] or graph[curNode].empty()) continue;
        proc[curNode] = true;
        if (curNode < n) {
            desequilibrium += (*(graph[curNode].begin()))->strength; 
        }
        else {
            desequilibrium -= (*(graph[curNode].begin()))->strength;
        }
        int newNode = (*(graph[curNode].begin()))->nA;
        if (newNode == curNode) newNode = (*(graph[curNode].begin()))->nB;
        graph[newNode].erase(graph[newNode].find(*(graph[curNode].begin())));
        graph[curNode].clear();
        if (graph[newNode].size() == 1) {
            q.push(newNode);
        }
    }
    desequilibrium = max(desequilibrium, -desequilibrium);

    for (int i = 0; i < 2*n; i++) {
        if (!proc[i] and graph[i].size() == 0) {
            cout << "NO";
            return 0;
        }
    }

    vector<int> desequilibriums;
    desequilibriums.push_back(desequilibrium);
    int desequilibriumsSum = desequilibrium;
    for (int i = 0; i < n; i++) {
        if (proc[i]) continue;
        int locDesiquilibrium = 0;
        int curNode = i;
        int parentNode = -1;
        int step = 1;
        while (!proc[curNode]) {
            proc[curNode] = true;
            int newNode = (*(graph[curNode].begin()))->nA;
            if (newNode == curNode) newNode = (*(graph[curNode].begin()))->nB;
            if (newNode == parentNode) {
                newNode = (*(next(graph[curNode].begin())))->nA;
                if (newNode == curNode) newNode = (*(next(graph[curNode].begin())))->nB;
                locDesiquilibrium += step*(*(next(graph[curNode].begin())))->strength;
            }
            else {
                locDesiquilibrium += step*(*(graph[curNode].begin()))->strength;
            }
            if (step == 1) step = -1;
            else step = 1;
            parentNode = curNode;
            curNode = newNode;
        }
        locDesiquilibrium = max(locDesiquilibrium, -locDesiquilibrium);
        desequilibriums.push_back(locDesiquilibrium);
        desequilibriumsSum += locDesiquilibrium;
    }

    bit = bitset<siz>(0);
    bit[0] = 1;
    for (int i : desequilibriums) {
        bit |= bit<<i;
    }

    for (int i = 0; i < siz; i++) if (bit[i] and abs(i-(desequilibriumsSum-i)) <= tolerance) {
        cout << "YES";
        return 0;
    }

    cout << "NO";
    return 0;
}

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