Submission #1156012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156012		pudelos	Tug of War (BOI15_tug)	C++20	100 / 100	87 ms	7308 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, ok;
V<int> waga;

int zlicz[2][off+1];

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

void usun(int v, int kridx) {
  if(sz(con[v])==0) {
    cout << "sus\n";
    return;
  }
  if(sz(con[v])==1) {
    if(con[v][0].s==kridx) con[v].pop_back();
    else cout << "sus2\n";
    return;
  }
  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);
  ok.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(ok[v]) continue;
    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);
    ok[v]=1;
    if(sz(con[u])<=1) q.push(u);
  }

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

  V<pair<int, bool>> przed;

  FOR(i, 1, off) {
    while(zlicz[1][i]>=3) {
      zlicz[1][i]-=2;
      zlicz[1][2*i]++;
    }
    while(zlicz[0][i]>=2) {
      zlicz[0][i]-=2;
      zlicz[1][2*i]++;
    }

    FOR(_, 1, zlicz[0][i]) przed.pb({i, 0});
    FOR(_, 1, zlicz[1][i]) przed.pb({i, 1});
  }

  bitset<2*off+1> dp;
  dp[off]=1;
  for(auto &[x, opcjonalne] : przed) {
    if(opcjonalne) dp|=(dp<<x)|(dp>>x);
    else 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));
  }
  
  if(w<=k) cout << "YES\n";
  else cout << "NO\n";
}

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