Submission #873827

#	Time	Username	Problem	Language	Result	Execution time	Memory
873827		ArashJafariyan	Tug of War (BOI15_tug)	C++17	0 / 100	91 ms	4576 KiB

tug

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

typedef long long ll;
typedef array<int, 2> pii;

#define pb push_back
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()

const int N = 3e4 + 4;

int n, k;
bool vis[N << 1];
set<pii> g[N << 1];
bitset<N * 20> ks;

bool ok(int v) {
    pii u = *g[v].begin();
    if (g[v] == g[u[0]]) {
        pii w = *g[v].rbegin();
        ks = (ks << u[1]) | (ks << w[1]);
        return 0;
    }
    return 1;
}

int dfs(int v, int p, int r, int tp) {
    vis[v] = 1;
    pii u = *g[v].begin();
    
    if (u[0] != p && u[0] != r) {
        int res = dfs(u[0], v, r, tp);
        if (tp == 0 && v < n)
            res += u[1];
        else if (tp == 1 && u[0] < n)
            res += u[1];
        return res;
    }
    else if (u[0] != p && u[0] == r) {
        int res = 0;
        if (tp == 0 && v < n)
            res += u[1];
        else if (tp == 1 && u[0] < n)
            res += u[1];
        return res;
    }
    else { 
        u = *g[v].rbegin();
        if (u[0] != r) {
            int res = dfs(u[0], v, r, tp);
            if (tp == 0 && v < n)
                res += u[1];
            else if (tp == 1 && u[0] < n)
                res += u[1];
            return res;
        }
        else {
            int res = 0;
            if (tp == 0 && v < n)
                res += u[1];
            else if (tp == 1 && u[0] < n)
                res += u[1];
            return res;
        }
    }
}

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

    int sum = 0;
    cin >> n >> k;
    for (int i = 0; i < (n << 1); ++i) {
        int l, r, s;
        cin >> l >> r >> s;
        sum += s;
        --l, --r;
        g[l].insert({r + n, s});
        g[r + n].insert({l, s});
    }

    queue<int> ones;
    for (int i = 0; i < (n << 1); ++i) {
        if (!g[i].size()) {
            cout << "NO";
            return 0;
        }
        if (g[i].size() == 1) 
            ones.push(i);
    }

    ks[0] = 1;
    while (!ones.empty()) {
        int v = ones.front();
        pii e = *g[v].begin();
        g[v].clear();
        ones.pop();

        if (v < n)
            ks <<= e[1];
        g[e[0]].erase(e);
        if (g[e[0]].size() == 1) 
            ones.push(e[0]);
        else if (!g[e[0]].size()) {
            cout << "NO";
            return 0;
        }
    }

    for (int i = 0; i < (n << 1); ++i) {
        if (g[i].size() != 0 && g[i].size() != 2) {
            cout << "NO";
            return 0;
        }
    }
    
    for (int i = 0; i < (n << 1); ++i) {
        if (!vis[i] && g[i].size() == 2 && ok(i)) {
            int res[2] = {dfs(i, i, i, 0), dfs(i, i, i, 1)};
            ks = (ks << res[0]) | (ks << res[1]);
        }
    }

    int mn = N * 20;
    for (int i = 0; i < N * 20; ++i) {
        if (ks[i]) {
            mn = min(mn, abs(i - (sum - i)));
            // cout << i << ' ';
        }
    }

    cout << (mn <= k ? "YES" : "NO");
    // cout << ' ' << mn << ' ' << sum;

    return 0;
}

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