Submission #79591

#	Time	Username	Problem	Language	Result	Execution time	Memory
79591		atoiz	Tug of War (BOI15_tug)	C++14	100 / 100	444 ms	31860 KiB

tug

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <stack>
#include <cstring>
#include <map>

using namespace std;

const int MAX = 100007, MAX_K = 500007, INF = 1e8;
int n, k, l[MAX], r[MAX], s[MAX], total = 0, inDeg[MAX];
bool used[MAX], sack[MAX_K], happy[MAX];
vector<int> inV[MAX];
map<int, int> packs;

void kill() { cout << "NO"; exit(0); }

signed main()
{
	// IO
	memset(used, 0, sizeof used);
	memset(happy, 0, sizeof happy);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < 2 * n; ++i) {
		cin >> l[i] >> r[i] >> s[i]; --l[i], --r[i], r[i] += n;
        inV[l[i]].push_back(i); ++inDeg[l[i]];
        inV[r[i]].push_back(i); ++inDeg[r[i]];
    }

    // remove singles
    stack<int> st;
    for (int p = 0; p < 2 * n; ++p) {
		if (inV[p].size() == 1) st.push(p);
    }

    int cur = 0;
    while (!st.empty()) {
        int p = st.top(); st.pop();
        used[p] = 1;
        int i;
        for (int x : inV[p]) {
            if (!happy[x]) {
				i = x;
				break;
            }
        }
        happy[i] = 1;

        int nxt;
        if (l[i] == p) cur += s[i], nxt = r[i];
        else cur -= s[i], nxt = l[i];

        --inDeg[nxt];
        if (inDeg[nxt] == 1) st.push(nxt);
	}


	// check & fix
    for (int p = 0; p < 2 * n; ++p) {
        if (used[p]) continue;
        if (inDeg[p] != 2) kill();
        vector<int> tmp; tmp.reserve(2);
        for (int i : inV[p]) if (!happy[i]) tmp.push_back(i);
        tmp.swap(inV[p]);
    }

    if (cur != 0) packs[abs(cur)] = 1;

	// initialize knapsack
    for (int p = 0; p < 2 * n; ++p) {
        if (used[p]) continue;

        int sgn = 1, cur = 0;
        int prv = (*inV[p].begin()), nxt = (*inV[p].rbegin());
        cur += sgn * s[prv]; sgn = -sgn; used[p] = 1;
		int p1 = (l[nxt] == p) ? r[nxt] : l[nxt];

        while (p1 != p) {
            prv = nxt;
            nxt = ((*inV[p1].begin()) == prv) ? (*inV[p1].rbegin()) : (*inV[p1].begin());
			cur += sgn * s[prv]; sgn = -sgn; used[p1] = 1;
            p1 = (l[nxt] == p1) ? r[nxt] : l[nxt];
        }

        cur = abs(cur);
        if (cur == 0) continue;
        if (packs.find(cur) == packs.end()) packs[cur] = 1;
        else ++ packs[cur];
	}

    memset(sack, 0, sizeof sack);
    sack[0] = 1;

    // total
    total = 0;
	for (map<int, int>::iterator it = packs.begin(); it != packs.end(); ++it) total += it->first * it->second;

    for (map<int, int>::iterator it = packs.begin(); it != packs.end(); ++it) {
        int val = it->first, cnt = it->second;
//        cerr << val << ' ' << cnt << endl;

        for (int start = 0; start < val; ++start) {
            int last = -INF;
            for (int i = start; i <= total / 2; i += val) {
                if (sack[i]) { last = i; continue; }
                if (last + val * cnt >= i) sack[i] = 1;
            }
        }
    }

    int i = total / 2;
    while (!sack[i]) --i;
    int ans = total - 2 * i;
//    cerr << ans << endl;

    if (ans <= k) cout << "YES";
    else cout << "NO";
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:53:46: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (l[i] == p) cur += s[i], nxt = r[i];
                                           ~~~^

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