Submission #492421

#TimeUsernameProblemLanguageResultExecution timeMemory
492421RainbowbunnyTug of War (BOI15_tug)C++17
100 / 100
967 ms21128 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 30005; int n, k; int l[2 * MAXN], r[2 * MAXN], s[2 * MAXN]; int pa, sum; set <int> Adj[2 * MAXN]; set <int> D[2 * MAXN]; bool Used[2 * MAXN]; bitset <20 * MAXN> dp; int c[2]; vector <int> N[2 * MAXN]; bool filled[2 * MAXN]; void DFS(int node, int color, int p = -1) { c[color] += s[node]; Used[node] = true; for(auto x : N[node]) { if(!Used[x]) { DFS(x, 1 - color, node); } } } int main() { // freopen("Input.txt", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); priority_queue <pair <int, int> > pq; cin >> n >> k; for(int i = 1; i <= 2 * n; i++) { cin >> l[i] >> r[i] >> s[i]; sum += s[i]; Adj[l[i]].emplace(i); Adj[r[i] + n].emplace(i); D[l[i]].insert(i); D[r[i] + n].insert(i); } for(int i = 1; i <= 2 * n; i++) { pq.emplace(-(int)D[i].size(), i); } while(pq.empty() == false) { int node = pq.top().second; if(pq.top().first < -1) { break; } // cout << node << endl; pq.pop(); if(D[node].empty()) { cout << "NO\n"; return 0; } int tt = *D[node].begin(); if(node <= n) { pa += s[tt]; } Used[tt] = true; D[l[tt]].erase(tt); D[r[tt] + n].erase(tt); Adj[l[tt]].erase(tt); Adj[r[tt] + n].erase(tt); filled[node] = true; if(!filled[l[tt]]) { pq.emplace(-(int)D[l[tt]].size(), l[tt]); } if(!filled[r[tt] + n]) { pq.emplace(-(int)D[r[tt] + n].size(), r[tt] + n); } } for(int i = 1; i <= 2 * n; i++) { if(Adj[i].size() == 2) { int t1 = *Adj[i].begin(); Adj[i].erase(Adj[i].begin()); int t2 = *Adj[i].begin(); Adj[i].erase(t2); N[t1].emplace_back(t2); N[t2].emplace_back(t1); } } dp[0] = 1; for(int i = 1; i <= 2 * n; i++) { if(!Used[i]) { c[0] = 0; c[1] = 0; DFS(i, 0); int tmp = min(c[0], c[1]); // cout << c[0] << ' ' << c[1] << endl; pa += tmp; dp = dp | (dp << (max(c[0], c[1]) - min(c[0], c[1]))); } } for(int i = 0; i <= sum; i++) { if(dp[i]) { int t1 = i + pa; int t2 = sum - t1; if(abs(t1 - t2) <= k) { cout << "YES\n"; return 0; } } } cout << "NO\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...