제출 #1191946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191946		asdasdqwer	Tug of War (BOI15_tug)	C++20	0 / 100	9 ms	2632 KiB

tug

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

#define pii array<int,2>

int main() {
    int n,k;cin>>n>>k;
    vector<set<pii>> g(2*n);
    for (int i=0;i<2*n;i++) {
        int l, r, s;cin>>l>>r>>s;
        l--;r--;
        r += n;
        g[l].insert({r, s});
        g[r].insert({l, s});
    }

    queue<int> q;
    int tot = 0;

    for (int i=0;i<2*n;i++) {
        if (g[i].size() == 1) {
            q.push(i);
        }
    }

    vector<bool> vis(2*n, false);

    while (!q.empty()) {
        int t=q.front();q.pop();
        if (g[t].size() != 1) {
            cout << "NO\n";
            return 0;
        }

        pii tmp = *g[t].begin();
        g[t].erase(g[t].find(tmp));

        g[tmp[0]].erase(g[tmp[0]].find({t, tmp[1]}));

        vis[t] = true;
        if (g[tmp[0]].size() == 1) {
            q.push(tmp[0]);
        }

        if (t < n) {
            tot -= tmp[1];
        }

        else {
            tot += tmp[1];
        }
    }

    for (int i=0;i<2*n;i++) {
        if (g[i].size() != 2 && !vis[i]) {
            cout << "NO\n";
            return 0;
        }
    }

    vector<int> weigh;

    for (int i=0;i<2*n;i++) {
        if (g[i].size() == 0) continue;

        int pt = i;
        int we = 0;
        int it = 0;
        while (g[pt].size()) {
            pii tmp = *g[pt].begin();
            g[pt].erase(g[pt].find(tmp));
            g[tmp[0]].erase(g[tmp[0]].find({pt, tmp[1]}));

            if (it % 2 == 0) we += tmp[1];
            else we -= tmp[1];

            it++;
            pt = tmp[0];
        }

        we = abs(we);
        weigh.push_back(we);
    }

    bitset<1'000'010> bt;
    const int MID = 500'002;

    bt[MID + tot] = 1;

    for (auto &x:weigh) {
        bt = ((bt << x) | (bt >> x));
    }

    bool pos = false;
    for (int i=0;i<=k;i++) {
        if (bt[MID + i] || bt[MID - i]) {
            pos = true;
        }
    }

    if (pos) {
        cout << "YES\n";
    }

    else {
        cout << "NO\n";
    }

}

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