Submission #652407

#	Time	Username	Problem	Language	Result	Execution time	Memory
652407		dooompy	Hacker (BOI15_hac)	C++17	0 / 100	5 ms	5332 KiB

hac

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

multiset<pair<int, int>> adj[100005];
bitset<600005*2> possible;

bool done[100005];

int curct;

void dfs(int node, int par = 1) {
    if (adj[node].empty()) return;

    auto cur = *adj[node].begin();
    adj[node].erase(adj[node].begin());
    adj[cur.first].erase(adj[cur.first].find({node, cur.second}));

    curct += par * cur.second;
    dfs(cur.first, -par);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= 2 * n; i++) {
        int l, r, s; cin >> l >> r >> s;
        r += n;
        adj[l].insert({r, s});
        adj[r].insert({l, s});
    }

    vector<int> must;

    for (int i = 1; i <= 2 * n; i++) {
        if (adj[i].empty()) {
            cout << "NO" << endl;
            return 0;
        }

        if (adj[i].size() == 1) {
            must.push_back(i);
        }
    }

    int ct = 0;

    while (!must.empty()) {
        auto cur = must.back(); must.pop_back();

        auto to = *adj[cur].begin();
        adj[cur].clear();

        if (cur > n) {
            ct += to.second;
        } else ct -= to.second;

        adj[to.first].erase(adj[to.first].find({cur, to.second}));
        if (adj[to.first].size() == 1) must.push_back(to.first);

    }

    int base = 600000 + ct;
    possible.set(base);

    for (int i = 1; i <= 2 * n; i++) {
        if (adj[i].empty()) {
            continue;
        }

        auto cur = *adj[i].begin();
        adj[i].erase(adj[i].begin());
        adj[cur.first].erase(adj[cur.first].find({i, cur.second}));

        curct = -cur.second;
         dfs(i);

         curct = abs(curct);

        possible = (possible << curct) | (possible >> curct);
    }

    for (int i = -k; i <= k; i++) {
        if (0 <= 600000 + i && 600000 + i < 1200001 && possible[600000 + i]) {
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 40