Submission #406130

#TimeUsernameProblemLanguageResultExecution timeMemory
406130codebuster_10Tug of War (BOI15_tug)C++17
41 / 100
293 ms3052 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(){ cout << "NO"; exit(0); } const int MX = 20 * 60000 + 1; signed main(){ setIO() ; int n,K; rd(n,K); vt<tuple<int,int,int>> g[2*n]; // {node,weight,id of edge} f(id,0,2*n){ int l,r,s; rd(l,r,s); --l,--r; g[l].eb(r+n,s,id); g[r+n].eb(l,s,id); } vt<bool> vis(2*n,false), vis_node(2*n,false); vt<int> W; f(k,0,2*n) if(!vis_node[k]){ int x = 0, edges = 0, nodes = 0; function<void(int)> dfs=[&](int i){ ++nodes; vis_node[i] = true; for(auto [j,w,id] : g[i]) if(!vis[id]){ vis[id] = true; ++edges; if(j<n) x += w; else x -= w; if(!vis_node[j]) dfs(j); } }; dfs(k); if(nodes != edges) err(); W.pb(abs(x)); } int sum = accumulate(all(W),0); bitset<MX> is; is[0] = true; for(auto i : W) is |= (is << i); f(i,0,MX){ if(abs(sum - 2*i) <= K && is[i]){ cout << "YES"; exit(0); } } err(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...