제출 #652407

#제출 시각아이디문제언어결과실행 시간메모리
652407dooompyHacker (BOI15_hac)C++17
0 / 100
5 ms5332 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...