Submission #1225551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225551		i_love_spring	Tug of War (BOI15_tug)	C++20	100 / 100	483 ms	36988 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ar array
const int N = 600005;
int n,k,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];
  d += cost;
  if (!visited[v]) {
    g[v].erase(g[v].find({u,-cost}));
    g[u].clear();
    dfs(v);
  }
 // g[u].clear();
}
void solve() {
  cin >> n >> k;
  memset(visited,0,sizeof(visited));
  // making graph , let's nodes of this graph denotes places, and edges denotes people
  for (int i = 1; i <= n * 2;i++) {
    int l, r, s;
    cin >> l >> r >> s;
    g[l].insert({r + n,s});
    g[r + n].insert({l,-s});
  }
  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].size()) {
      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
  int sum = accumulate(vals.begin(),vals.end(),0);
  dp[0] = true;
  for (int x : vals) dp |= (dp << abs(x));
  for (int i = 0; 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: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29