Submission #1225546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225546		i_love_spring	Tug of War (BOI15_tug)	C++20	23 / 100	170 ms	33436 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ar array
const int N = 600005;
int n,k,w1[N],w2[N],s[N],visited[N];
multiset<ar<int,2>>g[N];
bitset<N> dp;
ll d = 0;
void dfs(int u) {
  visited[u] = 1;
  if (!g[u].size()) return;
  int v = (*g[u].begin())[0] ,cost =(*g[u].begin())[1];
  if (!visited[v]) {
    g[v].erase(g[v].find({u,-cost}));
    d += cost;
    dfs(v);
  }
  g[u].clear();
}
void solve() {
  cin >> n >> k;
  memset(visited,0,sizeof(visited));
  for (int i = 1; i <= n * 2;i++) cin >> w1[i] >> w2[i] >> s[i];
  // making graph , let's nodes of this graph denotes places, and edges denotes people
  for (int i = 1; i <= n * 2;i++) g[w1[i]].insert({w2[i] + n,s[i]}),g[w2[i] + n].insert({w1[i],-s[i]});
  for (int i = 1; i <= n * 2;i++) {
    if (g[i].empty()) { // if nobody wants this place 
      cout << "NO";
      return;
    }
  }
  queue<int> q;
  for (int i = 1; i <= n * 2;i++) {
    if (g[i].size() == 1) q.push(i); // if there's only one person who wants this place
  }
  d = 0;
  while (!q.empty()) {
    int u = q.front(); // u is place not person
    q.pop();
    if (g[u].size() == 0) {
      cout << "NO";
      return;
    }
    int v = (*g[u].begin())[0] ,cost =(*g[u].begin())[1];
    d += cost;
    // cost will be opposite
    g[u].clear();
    g[v].erase(g[v].find({u,-cost}));
    if (g[v].size() == 1) q.push(v);
  }
  vector<ll>vals;
  if (d) vals.push_back(abs(d));
  for (int i = 1; i <= n * 2;i++) {
    // we know that every single node belong to exactly one componenent that is full of cycle, so we just go dfs , and remove this edges
    if (!visited[i] && !g[i].empty()) {
      d = 0;
      g[i].erase(g[i].begin()); // this edge is redundant 
      dfs(i);
      if (d) vals.push_back(abs(d));
    }
  }
  // can we divide vals into two subset S and T  , sum(S) - sum(T) <= k , sum(vals) - 2 * sum(S) <= k
  ll sum = accumulate(vals.begin(),vals.end(),0ll);
  dp[0] = true;
  sort(vals.begin(),vals.end());
  for (ll x : vals) dp |= (dp << x);
  for (int i = 1; i  <= sum;i++) {
    if (dp[i] && abs(sum - 2 * i) <= k) {
      cout << "YES";
      return;
    }
  }
  cout << "NO";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
} 

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