# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1210775 | quocbaoo | Tug of War (BOI15_tug) | C++20 | 327 ms | 5864 KiB |
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
int l[60004],r[60004],s[60004],dp[60004],d[60004],p[60004];
bool kt[60004],vs[60004];
int sum=0,s1=0,s2=0;
multiset<pair<int,int>> g[60004];int n,k;
bitset<600004> pos,lu;
void dfs(int i){
vs[i]=true;
if (g[i].size()==0) return;
int nx=(*g[i].begin()).fi,co=(*g[i].begin()).se;
sum+=co;
// cout<<i<<" "<<nx<<" "<<co<<endl;
if (i<=n) s1+=co;else s2+=co;
if (g[nx].size()>0) g[nx].erase(g[nx].find({i,co}));
g[i].clear() ;
dfs(nx);
}
int main(){
if (fopen("peri.in","r")){
freopen("peri.in","r",stdin);
freopen("peri.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for (int i=1;i<=2*n;i++){
cin>>l[i]>>r[i]>>s[i];
dp[l[i]]++;dp[n+r[i]]++;
d[l[i]]=i;p[n+r[i]]=i;
}
int A=0,B=0;
for (int i=1;i<=2*n;i++){
if (dp[i]==1) {
if (i<=n) A+=s[d[i]],kt[d[i]]=true;else B+=s[p[i]],kt[p[i]]=true;
// cout<<i<<" ";
}
if (dp[i]==0){
cout<<"NO";return 0;
}
}
for (int i=1;i<=2*n;i++){
if (kt[i]==false){
g[l[i]].insert({n+r[i],s[i]});
g[n+r[i]].insert({l[i],s[i]});
}
}
for (int i=1;i<=2*n;i++) if (g[i].size()!=2){
cout<<"NO";return 0;
}
pos[0]=1;
for (int i=1;i<=2*n;i++){
if (vs[i]==false){
s1=0;s2=0;
dfs(i);
lu=pos;pos|=(lu<<s1);pos|=(lu<<s2);
}
}
for (int i=0;i<=sum;i++){
if (pos[i]==1&&abs(A-B+2*i-sum)<=k){
cout<<"YES";return 0;
}
}
cout<<"NO";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |