Submission #589759

#	Time	Username	Problem	Language	Result	Execution time	Memory
589759		loctildore	Tug of War (BOI15_tug)	C++14	100 / 100	2200 ms	10892 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
int n,k,ori=600069;
int l[60069],r[60069],s[60069];
bool done[60069];
set<int> grph[60069];
bitset<600069*2> bst;
void check(int x) {
  if (done[x]) {
    return;
  }
  if (grph[x].size()==0) {
    cout<<"NO"<<endl;
    exit(0);
  }
  if (grph[x].size()!=1) {
    return;
  }
  done[x]=true;
  int i=*grph[x].begin();
  ori+=(x<n?-s[i]:s[i]);
  grph[l[i]].erase(i);
  grph[r[i]].erase(i);
  check(l[i]);
  check(r[i]);
}
int dfs(int x, int lst=-1) {
  if (done[x]) {
    return 0;
  }
  done[x]=true;
  for (auto i : grph[x]) {
    if (l[i]!=lst&&l[i]!=x) {
      return s[i]-dfs(l[i],x);
    }
    if (lst==l[i]) {
      lst=-1;
    }
    if (r[i]!=lst&&r[i]!=x) {
      return s[i]-dfs(r[i],x);
    }
    if (lst==r[i]) {
      lst=-1;
    }
  }
  return 0;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>k;
  for (int i = 0; i < 2*n; i++) {
    cin>>l[i]>>r[i]>>s[i];
    l[i]--;r[i]--;
    r[i]+=n;
    grph[l[i]].insert(i);
    grph[r[i]].insert(i);
  }
  for (int i = 0; i < 2*n; i++) {
    check(i);
  }
  bst[ori]=true;
  for (int i = 0; i < 2*n; i++) {
    if (done[i]) {
      continue;
    }
    int tmp=dfs(i);
    tmp=abs(tmp);
    bst=bst<<tmp;
    bst|=bst>>(2*tmp);
  }
  for (int i = 600069-k; i <= 600069+k; i++) {
    if (bst[i]) {
      cout<<"YES"<<endl;
      return 0;
    }
  }
  cout<<"NO"<<endl;
  return 0;
}

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