Submission #949344

#	Time	Username	Problem	Language	Result	Execution time	Memory
949344		UmairAhmadMirza	Tug of War (BOI15_tug)	C++17	23 / 100	23 ms	8016 KiB

tug

#include <bits/stdc++.h>
using namespace std;
int const N=30005;
int const maxx=6e5;
set<int> mem[2*N];
set<pair<int,int>> sz;
int L[2*N],R[2*N],S[2*N];
bool done[2*N];
bool dp[maxx];
bool tmdp[maxx];
bool check(vector<int> ds,int k,int s1,int s2){
  dp[0]=1;
  for(auto i:ds){
    for(int j=0;j<maxx;j++)
      tmdp[j]=0;
    for(int j=0;j<maxx;j++){
      if(dp[j]){
        tmdp[j+i]=1;
        tmdp[abs(j-i)]=1;
      }
    }
    for(int j=0;j<maxx;j++)
      dp[j]=tmdp[j];
  }
  for(int i=0;i<=maxx;i++)
    if(dp[i] && (abs((i+s1)-s2)<=k || abs((i+s2)-s1)<=k))
      return 1;
  return 0;
}
int main() 
{
  int n,k;
  cin>>n>>k;
  for(int i=1;i<=2*n;i++){
    int s,l,r;
    cin>>l>>r>>s;
    r+=n;
    mem[l].insert(i);
    mem[r].insert(i);
    L[i]=l;
    R[i]=r;
    S[i]=s;
  }
  for(int i=1;i<=2*n;i++)
    sz.insert({mem[i].size(),i});
  int sum1=0,sum2=0;
  while(sz.size()){
    auto p=*(sz.begin());
    int job=p.second;
    int cons=p.first;
    // cout<<job<<' '<<cons<<endl;
    if(cons==2)
      break;
    sz.erase(sz.begin());
    if(cons==0){
      cout<<"NO"<<endl;
      return 0;
    }
    else if(cons==1){
      int per=*(mem[job].begin());
      if(job<=n)
        sum1+=S[per];
      else
        sum2+=S[per];
      // cout<<per<<' '<<L[per]<<' '<<R[per]<<endl;
      sz.erase({mem[L[per]].size(),L[per]});
      sz.erase({mem[R[per]].size(),R[per]});
      mem[L[per]].erase(per);
      mem[R[per]].erase(per);
      if(done[L[per]]==0 && L[per]!=job)
        sz.insert({mem[L[per]].size(),L[per]});
      if(done[R[per]]==0 && R[per]!=job)
        sz.insert({mem[R[per]].size(),R[per]});
      done[job]=1;
    }
    else
      break;
  }
  
  //now all are with degree two.
  vector<int> ds;
  int temp=0;
  while(sz.size()){
    auto p=*(sz.begin());
    int job=p.second;
    int cons=p.first;
    // cout<<job<<' '<<cons<<endl;
    sz.erase(sz.begin());
    if(cons==2 && temp!=0){
      ds.push_back(abs(temp));
      temp=0;
    }
    int per=*(mem[job].begin());
    if(job<=n)
      temp+=S[per];
    else
      temp-=S[per];
      // cout<<per<<' '<<L[per]<<' '<<R[per]<<endl;
    sz.erase({mem[L[per]].size(),L[per]});
    sz.erase({mem[R[per]].size(),R[per]});
    mem[L[per]].erase(per);
    mem[R[per]].erase(per);
    if(done[L[per]]==0 && L[per]!=job)
      sz.insert({mem[L[per]].size(),L[per]});
    if(done[R[per]]==0 && R[per]!=job)
      sz.insert({mem[R[per]].size(),R[per]});
    done[job]=1;
  }
  if(temp!=0)
    ds.push_back(abs(temp));
  // make a sum <= k from ds;
  
  if(check(ds,k,sum1,sum2))
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
  return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29