Submission #890757

#TimeUsernameProblemLanguageResultExecution timeMemory
890757zeta7532Tug of War (BOI15_tug)C++17
41 / 100
124 ms1880 KiB
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll = long long; const ll mod = 998244353; #define fi first #define se second #define rep(i,n) for(ll i=0;i<n;i++) #define all(x) x.begin(),x.end() #define faster ios::sync_with_stdio(false);cin.tie(nullptr) struct unionfind{ unionfind() {} vector<ll> par,sz; unionfind(ll n):par(n),sz(n){ for(ll i=0;i<n;i++) par[i]=i, sz[i]=1; } ll root(ll x){ if(par[x]==x) return x; ll t=root(par[x]); par[x]=t; return t; } ll size(ll x){ return sz[x]; } void unite(ll x,ll y){ ll rx=root(x); ll ry=root(y); if(rx==ry) return; if (sz[rx]>sz[ry]) swap(rx,ry); par[rx]=ry;sz[ry]+=sz[rx]; } bool same(ll x,ll y){ ll rx=root(x); ll ry=root(y); return rx==ry; } }; int main() { ll N,K; cin >> N >> K; N*=2; vector<ll> l(N),r(N),s(N); ll max_s=0; rep(i,N){ cin >> l[i] >> r[i] >> s[i]; l[i]--,r[i]--; max_s=max(max_s,s[i]); } if(N<=20){ bool ans=false; rep(bit,1<<N){ vector<ll> L(N/2,-1),R(N/2,-1); rep(i,N){ if(bit&(1<<i)) L[l[i]]=i; else R[r[i]]=i; } ll cnt_l=0,cnt_r=0; rep(i,N/2){ if(L[i]==-1){ cnt_l=-1; break; } cnt_l+=s[L[i]]; } rep(i,N/2){ if(R[i]==-1){ cnt_r=-1; break; } cnt_r+=s[R[i]]; } if(cnt_l==-1||cnt_r==-1) continue; if(abs(cnt_l-cnt_r)<=K) ans=true; } if(ans) cout << "YES" << endl; else cout << "NO" << endl; return 0; } if(max_s==1){ unionfind tree(N); rep(i,N) tree.unite(l[i],r[i]+N/2); vector<ll> cnt(N,0); rep(i,N) cnt[tree.root(l[i])]++; bool ans=true; rep(i,N){ if(tree.root(i)!=i) continue; if(cnt[i]!=tree.size(i)) ans=false; } if(ans) cout << "YES" << endl; else cout << "NO" << endl; return 0; } return 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...