Submission #1218679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218679		faruk	Tug of War (BOI15_tug)	C++20	100 / 100	1452 ms	10516 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<multiset<pii> > graph;

int tot = 0;
void dfs(int curr) { // if i'm here I have degree 1
    pii to = *graph[curr].begin();
    graph[curr].erase(to);
    graph[to.first].erase(graph[to.first].find(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;
void do_cyc(int curr, int &diff, bool add) {
    if (vis[curr])
        return;
    vis[curr] = true;
    pii to = *graph[curr].begin();
    graph[curr].erase(graph[curr].begin());
    int t = to.first, s = to.second;
    if (add)
        diff += s;
    else
        diff -= s;
    graph[t].erase(graph[t].find(mp(curr, s)));
    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);
    }

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

    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])
        {
            do_cyc(i, diff, false);
            diff = abs(diff);
            sizs.push_back(diff * 2);
            tot -= diff;
        }
    }

    bitset<maxsiz> dp;
    dp[offset + tot] = 1;
    for (int i : sizs)
        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

// 5 3 1
// -9 + 10

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