Submission #1173441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173441		akamizane	Tug of War (BOI15_tug)	C++20	48 / 100	33 ms	5704 KiB

tug

#include<bits/stdc++.h>
using namespace std;

#define debug(...) 42

#define int long long
using ll = long long;

const int maxn = 6e4 + 1;

multiset<pair<int,int>> ad[maxn];
bitset<600001> dp;
bool vis[maxn];
int tot = 0;

void dfs(int u){
  vis[u] = true;
  if (!ad[u].size()) return;
  auto [v, w] = *ad[u].begin();
  tot += w;
  if (!vis[v]){
    ad[v].erase(ad[v].find({u, -w}));
    ad[u].clear();
    dfs(v);
  }
}

void solve(){
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < 2 * n; i++){
    int l, r, s;
    cin >> l >> r >> s;
    ad[l].insert({n + r, s});
    ad[n + r].insert({l, -s});
  }
  queue<int> q;
  for (int i = 1; i <= 2 * n; i++){
    if (ad[i].size() == 1) q.push(i);
    if (ad[i].size() == 0){
      cout << "NO\n";
      return;
    }
  }
  while(q.size()){
    auto cur = q.front();
    q.pop();
    if (ad[cur].size() == 0){
      cout << "NO\n";
      return;
    } 
    auto [v, w] = *ad[cur].begin();
    tot += w;
    ad[cur].clear();
    ad[v].erase(ad[v].find({cur, -w}));
    if (ad[v].size() == 1) q.push(v);
  }
  vector<int> val;
  if (tot != 0) val.push_back(abs(tot));
  for (int i = 1; i <= 2 * n; i++){
    if (!vis[i] && ad[i].size()){
      tot = 0;
      ad[i].erase(ad[i].begin());
      dfs(i);
      if (tot) val.push_back(abs(tot));
    }
  }
  int sum = accumulate(val.begin(), val.end(), 0ll);
  dp[0] = 1;
  for (auto x : val) dp |= dp << x;
  for (int i = 1; i <= sum; i++){
    if (dp[i] && abs(2 * i - sum) <= k){
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt--){
    solve();
  }
  return 0;
}

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