제출 #1218653

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

tug

#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxsiz = 30000 * 20 * 3;
const int offset = 30000 * 10 * 3;

int n;
vector<int> l, r, s;
vector<set<pii> > graph;

int tot = 0;
void dfs(int curr) { // if i'm here I have degree 1
    pii to = *graph[curr].begin();
    graph[to.first].erase(pii(curr, to.second));
    if (curr < n)
        tot += to.second;
    else
        tot -= to.second;

    if (graph[to.first].size() == 1)
        dfs(to.first);
}

vector<bool> vis;
int beg = 0;
void do_cyc(int curr, int &diff, bool add) {
    vis[curr] = true;
    for (auto [t, s] : graph[curr]) {
        if (vis[t] and t != beg)
            continue;
        if (add)
            diff += s;
        else
            diff -= s;
        if (t != beg)
            do_cyc(t, diff, !add);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int k;
    cin >> n >> k;
    l = r = s = vector<int>(n * 2);
    vis = vector<bool>(n * 2);
    graph.resize(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> l[i] >> r[i] >> s[i];
        l[i]--, r[i]--;
        graph[l[i]].insert(mp(r[i] + n, s[i]));
        graph[r[i] + n].insert(mp(l[i], s[i]));
    }

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

    vector<int> sizs;
    for (int i = 0; i < 2 * n; i++) {
        if (graph[i].size() == 0)
            continue;
        if (graph[i].size() != 2)
        {
            cout << "NO\n";
            return 0;
        }
        int diff = 0;
        if (!vis[i])
        {
            beg = i;
            do_cyc(i, diff, false);
            sizs.push_back(diff * 2);
            tot -= diff;
        }
    }

    bitset<maxsiz> dp;
    dp[offset + tot] = 1;
    for (int i : sizs)
    {
        if (i > 0)
            dp |= dp >> i;
        else
            dp |= dp << (-i);
    }
    
    for (int i = offset - k; i <= offset + k; i++) {
        if (dp[i])
        {
            cout << "YES\n";
            return 0;
        }
    }
    
    cout << "NO\n";
}


// d + tot_sum - chosen * 2
// |-d - tot_sum + chosen*2| <= K

// 4 5 2
// 

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