Submission #51972

#	Time	Username	Problem	Language	Result	Execution time	Memory
51972		mareksom	Tug of War (BOI15_tug)	C++17	100 / 100	1052 ms	24516 KiB

tug

#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (c it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "

using ld = long double;
using ll = long long;

constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;

void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }

template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }

void Odp(bool ok) {
  if (ok) cout << "YES" << endl;
  else cout << "NO" << endl;
  exit(0);
}

int diff, k;
vector<int> roznice;
bitset<600 * 1000 + 105> ok;

void Podzial() {
  const int a = -k - diff;
  const int b = k - diff;
  debug() << imie(a) imie(b) imie(roznice);
  if (b < 0) Odp(false);
  if (a <= 0) Odp(true);
  assert(a <= b);
  if (b >= (int) ok.size()) Odp(false);
  for (int i = a; i <= b; i++) {
    ok[i] = 1;
  }
  for (int r : roznice) {
    ok |= (ok >> r);
    if (ok[0]) Odp(true);
  }
  Odp(false);
}

constexpr int nax = 60 * 1000 + 105;

int n;
vector<pair<int, int>> graf[nax];
bool odw[nax];
bool nacyk[nax];
bool nacyklu[nax];
vector<pair<int, int>> cykl;

bool Cykl(int w, int o) {
  if (nacyk[w]) {
    reverse(cykl.begin(), cykl.end());
    while (cykl.back().first != w) {
      cykl.pop_back();
    }
    reverse(cykl.begin(), cykl.end());
    return true;
  }
  if (odw[w]) return false;
  odw[w] = true;
  nacyk[w] = true;
  for (auto& it : graf[w]) {
    if (it.first == o) {
      o = -1;
      continue;
    }
    cykl.emplace_back(w, it.second);
    if (Cykl(it.first, w)) {
      return true;
    }
    cykl.pop_back();
  }
  nacyk[w] = false;
  return false;
}

void Dfs(int w, int o, int kraw) {
  if (1 <= w and w <= n) {
    diff += kraw;
  } else if (n + 1 <= w and w <= 2 * n) {
    diff -= kraw;
  } else {
    assert(false);
  }
  odw[w] = true;
  for (auto& it : graf[w]) {
    if (it.first != o) {
      Dfs(it.first, w, it.second);
    }
  }
}

void OdpalZ(int w) {
  debug() << "OdpalZ(" imie(w) ")";
  if (!Cykl(w, -1)) assert(false);
  debug() << imie(cykl);
  for (auto& nac : cykl) {
    nacyklu[nac.first] = true;
    odw[nac.first] = true;
  }
  for (auto& nac : cykl) {
    for (auto& it : graf[nac.first]) {
      if (!nacyklu[it.first]) {
        Dfs(it.first, nac.first, it.second);
      }
    }
  }
  assert((int) cykl.size() % 2 == 0);
  int roznica = 0;
  for (int i = 0; i < (int) cykl.size(); i++) {
    const int val = cykl[i].second;
    if (i % 2 == 0) roznica += val;
    else roznica -= val;
  }
  roznica = abs(roznica);
  diff -= roznica;
  roznica *= 2;
  roznice.push_back(roznica);
}

void Grafuj() {
  for (int i = 1; i <= n; i++) {
    if (!odw[i]) {
      OdpalZ(i);
    }
  }
}

int rozmiar[nax];
bool jest_cykl[nax];
int fut[nax];
int fuf(int w) { if (fut[w] == w) return w; return fut[w] = fuf(fut[w]); }
void fuu(int u, int v) {
  u = fuf(u);
  v = fuf(v);
  if (u == v) {
    if (jest_cykl[u]) {
      Odp(false);
    }
    jest_cykl[u] = true;
    return;
  }
  rozmiar[u] += rozmiar[v];
  if (jest_cykl[v] and jest_cykl[u]) {
    Odp(false);
  }
  if (jest_cykl[v]) jest_cykl[u] = true;
  fut[v] = u;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= 2 * n; i++) {
    fut[i] = i;
    rozmiar[i] = 1;
  }
  for (int i = 1; i <= 2 * n; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    b += n;
    graf[a].emplace_back(b, c);
    graf[b].emplace_back(a, c);
    fuu(a, b);
  }
  Grafuj();
  Podzial();
  return 0;
}

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