Submission #1155902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155902		pudelos	Tug of War (BOI15_tug)	C++20	0 / 100	552 ms	3268 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define sz(A) (int)(A.size())
#define pi pair<int, int>
#define f first
#define s second
#define eb emplace_back
#define pb push_back
#define rs resize
#define V vector

const int off=6e5, inf=1e9;

int n, k;
int SL, SP;
V<V<pi>> con;
V<pi> ktora;
V<bool> vis;
V<int> waga;

void WA() {
  cout << "NO\n";
  exit(0);
}

void usun(int v, int kridx) {
  if(sz(con[v])==1) con[v].pop_back();
  if(v%2==0) {
    int poz = ktora[kridx].f;
    swap(con[v][poz], con[v].back());
    ktora[con[v][poz].s].f=poz;
    con[v].pop_back();  
  } else {
    int poz = ktora[kridx].s;
    swap(con[v][poz], con[v].back());
    ktora[con[v][poz].s].s=poz;
    con[v].pop_back(); 
  }
}

int locsl, locsp;
void dfs(int v) {
  for(auto &[u, kridx] : con[v]) {
    if(vis[kridx]) continue;
    if(v%2==0) locsl+=waga[kridx];
    else locsp+=waga[kridx];
    vis[kridx]=1;
    dfs(u);
  }
}

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> k;
  con.rs(2*n+1);
  waga.rs(2*n+1);
  ktora.rs(2*n+1);

  int cntkr=0;
  int l, r, s;
  FOR(i, 1, 2*n) {
    cin >> l >> r >> s;
    int a = 2*l;
    int b = 2*r-1;
    con[a].pb({b, ++cntkr});
    con[b].pb({a, cntkr});
    ktora[cntkr]={sz(con[a])-1, sz(con[b])-1};
    waga[cntkr]=s;
  }

  FOR(i, 1, 2*n) if(sz(con[i])==0) WA();
  queue<int> q;
  FOR(i, 1, 2*n) if(sz(con[i])==1) q.push(i);
  while(!q.empty()) {
    int v = q.front();
    q.pop();
    if(sz(con[v])==0) WA();
    if(sz(con[v])!=1) continue;
    auto [u, kridx] = con[v][0];
    if(v%2==0) SL+=waga[kridx];
    else SP+=waga[kridx];
    usun(v, kridx);
    usun(u, kridx);
    if(sz(con[u])<=1) q.push(u);
  }

  V<int> przed;

  vis.rs(2*n+1);
  FOR(i, 1, 2*n) {
    if(sz(con[i])==0) continue;
    locsl=0;
    locsp=0;
    dfs(i);
    int x = abs(locsl-locsp);
    przed.eb(x);    
  }

  bitset<2*off+1> dp;
  dp[off]=1;
  for(int x : przed) dp=(dp<<x)|(dp>>x);
  int w = inf;
  FOR(i, 0, 2*off) {
    if(dp[i]==0) continue;
    w=min(w, abs(SL-SP+i-off));
  }
  // cout << w << '\n';
  if(w<=k) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
}

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