제출 #1369423

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

tug

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

#define ff endl
#define lf "\n"
#define fi first
#define se second
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

#ifdef DEBUG

constexpr bool IS_DEBUG = 1;

#define infor(fmt, ...) do { print(stderr, fmt, ##__VA_ARGS__); } while(0)
#define infof(fmt, ...) do { println(stderr, fmt, ##__VA_ARGS__); } while(0)

#else

constexpr bool IS_DEBUG = 0;

#define infor(fmt, ...)
#define infof(fmt, ...)

#endif

using ll = long long;

using pll = pair<ll, ll>;
using pii = pair<int, int>;

template<typename... Args>
using vec = vector<Args...>;

mt19937 timmy_loves_gambling(73);

constexpr int MAXS = 6e5+7;

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

    int N, K; cin >> N >> K;

    vec<int> dg(2 * N);
    vec<vec<pii>> adj(2 * N);
    for(int i = 0; i < 2 * N; ++i) {
        int l, r, x; cin >> l >> r >> x;

        l -= 1, r += N - 1;

        adj[l].emplace_back(r, x);
        adj[r].emplace_back(l, x);

        dg[l] += 1, dg[r] += 1;
    }

    queue<int> q;
    for(int i = 0; i < 2 * N; ++i) {
        if(dg[i] != 1) continue;

        auto [j, x] = adj[i][0];

        if(dg[j] == 1) {
            cout << "NO" << lf;
            return 0;
        } else {
            q.emplace(i);
        }
    }

    int L = 0, R = 0, X = 0, Y = 0;
    while(!q.empty()) {
        auto u = q.front(); q.pop();

        for(auto [v, x]: adj[u]) {
            if(dg[v] == 1) continue;
            dg[v] -= 1;
            if(dg[v] != 1) continue;

            q.emplace(v);

            (v < N ? L : R) += x;
            (v < N ? X : Y) += 1;
        }
    }

    if(X != Y) {
        cout << "NO" << lf;
        return 0;
    }

    for(int i = 0; i < 2 * N; ++i) {
        if(dg[i] > 2) {
            cout << "NO" << lf;
            return 0;
        }
    }

    vec<bool> vis(2 * N);
    for(int i = 0; i < 2 * N; ++i) {
        vis[i] = dg[i] < 2;
    }

    auto dfs = [&](int u, auto &&dfs) -> int {
        vis[u] = 1;

        for(auto [v, x]: adj[u]) {
            if(vis[v]) continue;

            int y = dfs(v, dfs);

            return x - y;
        }

        return 0;
    };

    vec<int> W;
    for(int i = 0; i < 2 * N; ++i) {
        if(vis[i]) continue;

        int x = 0, f = -1;
        for(auto [j, y]: adj[i]) {
            if(vis[j] == 0) {
                x = y;
                f = j;
            }
        }

        int y = dfs(i, dfs);

        W.emplace_back(abs(x - y));
    }

    int S = accumulate(all(W), 0);

    bitset<MAXS> kp;
    kp[0] = 1;

    for(auto w: W) {
        kp |= kp << w;
    }

    int mn = INT_MAX;
    for(int i = 0; i <= S; ++i) {
        if(kp[i] == 0) continue;

        mn = min(mn, abs((L + i) - (R + S - i)));
    }

    cout << (mn <= K ? "YES" : "NO") << lf;
}

• 서브태스크 1: 0 / 18
• 서브태스크 2: 0 / 30
• 서브태스크 3: 0 / 23
• 서브태스크 4: 0 / 29