Submission #406320

#TimeUsernameProblemLanguageResultExecution timeMemory
406320codebuster_10Tug of War (BOI15_tug)C++17
0 / 100
21 ms5752 KiB
#include <bits/stdc++.h> using namespace std ; #define int int64_t //be careful about this #define endl "\n" #define f(i,a,b) for(int i=int(a);i<int(b);++i) #define pr pair #define ar array #define fr first #define sc second #define vt vector #define pb push_back #define eb emplace_back #define LB lower_bound #define UB upper_bound #define PQ priority_queue #define sz(x) ((int)(x).size()) #define all(a) (a).begin(),(a).end() #define allr(a) (a).rbegin(),(a).rend() #define mem0(a) memset(a, 0, sizeof(a)) #define mem1(a) memset(a, -1, sizeof(a)) template<class A> void rd(vt<A>& v); template<class T> void rd(T& x){ cin >> x; } template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;} template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;} template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template<typename T> void __p(T a) { cout<<a; } template<typename T, typename F> void __p(pair<T, F> a) { cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; } template<typename T> void __p(std::vector<T> a) { cout<<"{"; for(auto it=a.begin(); it<a.end(); it++) __p(*it),cout<<",}\n"[it+1==a.end()]; } template<typename T, typename ...Arg> void __p(T a1, Arg ...a) { __p(a1); __p(a...); } template<typename Arg1> void __f(const char *name, Arg1 &&arg1) { cout<<name<<" : "; __p(arg1); cout<<endl; } template<typename Arg1, typename ... Args> void __f(const char *names, Arg1 &&arg1, Args &&... args) { int bracket=0,i=0; for(;; i++) if(names[i]==','&&bracket==0) break; else if(names[i]=='(') bracket++; else if(names[i]==')') bracket--; const char *comma=names+i; cout.write(names,comma-names)<<" : "; __p(arg1); cout<<" | "; __f(comma+1,args...); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(cin.failbit); cout.precision(15); cout << fixed; #ifdef ONLINE_JUDGE if(sz(s)){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } #define __f(...) 0 #endif } void err(bool flag){cout << (flag?"YES":"NO"); exit(0);} const int MAX_N = 2 * 30000 + 1; multiset<pr<int,int>> g[MAX_N]; vt<bool> vis(MAX_N,false); bitset<MAX_N> is; int tot = 0; void dfs(int i) { vis[i] = true; if (!sz(g[i])) return; auto [nxt,cost] = *g[i].begin(); tot += cost; if (!vis[nxt]) { g[nxt].erase(g[nxt].find({i, -cost})); g[i].clear(); dfs(nxt); } } signed main(){ setIO() ; int n,k; rd(n,k); f(id,0,2*n){ int l,r,s; rd(l,r,s); --l,--r; g[l].insert({r+n,s}); g[r+n].insert({l,-s}); } // keep removing those with degree one. queue<int> q; f(i,0,n){ if(sz(g[i]) == 1) q.push(i); else if(sz(g[i]) == 0) err(0); } while(sz(q)){ int now = q.front(); q.pop(); if(!sz(g[now])) err(0); auto [nxt,cost] = *g[now].begin(); tot += cost; g[now].clear(); g[nxt].erase(g[nxt].find({now,-cost})); if(sz(g[nxt]) == 1) q.push(nxt); } vt<int> W; if(tot) W.pb(abs(tot)); f(i,0,n) if(!vis[i] && sz(g[i])){ tot = 0; g[i].erase(g[i].begin()); dfs(i); if(tot) W.pb(abs(tot)); } int sum = accumulate(all(W),0); is[0] = true; for(auto i : W) is |= (is << i); f(i,0,MAX_N){ if(abs(sum - 2*i) <= k && is[i]) err(1); } err(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...