test/yukicoder/274.UFPU.test.cpp

• View this file on GitHub
• Last update: 2024-09-21 22:25:10+09:00
• Problem: https://yukicoder.me/problems/no/274

Depends on

• Union-Find (ポテンシャル, undo可能) (src/DataStructure/UnionFind_Potentialized_Undoable.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/274
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// ポテンシャルUF(無向2SAT)
#include <iostream>
#include "src/DataStructure/UnionFind_Potentialized_Undoable.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 int L[N], R[N];
 for (int i= 0; i < N; ++i) cin >> L[i] >> R[i];
 UnionFind_Potentialized_Undoable<bool> uf(N);
 for (int i= N; i--;)
  for (int j= i; j--;) {
   if (!(R[i] < L[j] || R[j] < L[i]))
    if (!uf.unite(i, j, 1)) return cout << "NO" << '\n', 0;
   if (!(R[i] < M - 1 - R[j] || M - 1 - L[j] < L[i]))
    if (!uf.unite(i, j, 0)) return cout << "NO" << '\n', 0;
  }
 cout << "YES" << '\n';
 return 0;
}

#line 1 "test/yukicoder/274.UFPU.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/274
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// ポテンシャルUF(無向2SAT)
#include <iostream>
#line 2 "src/DataStructure/UnionFind_Potentialized_Undoable.hpp"
#include <vector>
#include <algorithm>
#include <cassert>
template <class weight_t> class UnionFind_Potentialized_Undoable {
 std::vector<int> par;
 std::vector<weight_t> val;
 std::vector<std::tuple<int, int, weight_t, int>> his;
 int cur;
public:
 UnionFind_Potentialized_Undoable(int n): par(n, -1), val(n), his{{-1, -1, weight_t(), 1}}, cur(0) { his.reserve(n + 1); }
 int leader(int u) const { return par[u] < 0 ? u : leader(par[u]); }
 //  -p(v) + p(u) = w
 bool unite(int u, int v, weight_t w) {
  if constexpr (std::is_same_v<weight_t, bool>) w^= potential(v) ^ potential(u);
  else w= potential(v) + w - potential(u);
  if (++cur; (u= leader(u)) == (v= leader(v))) return ++std::get<3>(his.back()), w == weight_t();
  if (par[v] > par[u]) std::swap(u, v), w= -w;
  return his.emplace_back(u, par[u], val[u], 1), par[v]+= par[u], par[u]= v, val[u]= w, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
 weight_t potential(int u) {
  if (par[u] < 0) return val[u];
  if constexpr (std::is_same_v<weight_t, bool>) return potential(par[u]) ^ val[u];
  else return potential(par[u]) + val[u];
 }
 //  -p(v) + p(u)
 weight_t diff(int u, int v) {
  if constexpr (std::is_same_v<weight_t, bool>) return potential(u) ^ potential(v);
  else return -potential(v) + potential(u);
 }
 int time() const { return cur; }
 void undo() {
  if (assert(cur > 0), --cur; --std::get<3>(his.back()) == 0) {
   auto [u, p, v, _]= his.back();
   par[par[u]]-= p, par[u]= p, val[u]= v, his.pop_back();
  }
 }
 void rollback(int t) {
  assert(0 <= t), assert(t <= cur);
  if (t == cur) return;
  for (;;) {
   auto &[u, p, v, i]= his.back();
   if (cur-= i; cur < t) {
    i= t - cur, cur= t;
    break;
   }
   par[par[u]]-= p, par[u]= p, val[u]= v, his.pop_back();
  }
 }
};
#line 7 "test/yukicoder/274.UFPU.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 int L[N], R[N];
 for (int i= 0; i < N; ++i) cin >> L[i] >> R[i];
 UnionFind_Potentialized_Undoable<bool> uf(N);
 for (int i= N; i--;)
  for (int j= i; j--;) {
   if (!(R[i] < L[j] || R[j] < L[i]))
    if (!uf.unite(i, j, 1)) return cout << "NO" << '\n', 0;
   if (!(R[i] < M - 1 - R[j] || M - 1 - L[j] < L[i]))
    if (!uf.unite(i, j, 0)) return cout << "NO" << '\n', 0;
  }
 cout << "YES" << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	98_challenge01.txt	AC	6 ms	4 MB
g++-13	99_system_test1.txt	AC	5 ms	4 MB
g++-13	99_system_test2.txt	AC	5 ms	3 MB
g++-13	99_system_test3.txt	AC	5 ms	4 MB
g++-13	99_system_test4.txt	AC	5 ms	3 MB
g++-13	challenge01.txt	AC	5 ms	4 MB
g++-13	sample1.txt	AC	5 ms	4 MB
g++-13	sample2.txt	AC	5 ms	4 MB
g++-13	sample3.txt	AC	5 ms	4 MB
g++-13	sample4.txt	AC	5 ms	4 MB
g++-13	system_test1.txt	AC	5 ms	4 MB
g++-13	test1.txt	AC	5 ms	4 MB
g++-13	test10.txt	AC	9 ms	4 MB
g++-13	test11.txt	AC	10 ms	4 MB
g++-13	test12.txt	AC	10 ms	4 MB
g++-13	test13.txt	AC	10 ms	4 MB
g++-13	test14.txt	AC	10 ms	4 MB
g++-13	test15.txt	AC	10 ms	4 MB
g++-13	test16.txt	AC	10 ms	4 MB
g++-13	test2.txt	AC	5 ms	4 MB
g++-13	test3.txt	AC	7 ms	4 MB
g++-13	test4.txt	AC	5 ms	4 MB
g++-13	test5.txt	AC	5 ms	4 MB
g++-13	test6.txt	AC	7 ms	4 MB
g++-13	test7.txt	AC	5 ms	4 MB
g++-13	test8.txt	AC	5 ms	4 MB
g++-13	test9.txt	AC	5 ms	4 MB
clang++-18	98_challenge01.txt	AC	5 ms	4 MB
clang++-18	99_system_test1.txt	AC	5 ms	4 MB
clang++-18	99_system_test2.txt	AC	5 ms	4 MB
clang++-18	99_system_test3.txt	AC	5 ms	4 MB
clang++-18	99_system_test4.txt	AC	5 ms	4 MB
clang++-18	challenge01.txt	AC	5 ms	4 MB
clang++-18	sample1.txt	AC	5 ms	4 MB
clang++-18	sample2.txt	AC	5 ms	4 MB
clang++-18	sample3.txt	AC	5 ms	4 MB
clang++-18	sample4.txt	AC	5 ms	4 MB
clang++-18	system_test1.txt	AC	5 ms	4 MB
clang++-18	test1.txt	AC	5 ms	4 MB
clang++-18	test10.txt	AC	9 ms	4 MB
clang++-18	test11.txt	AC	10 ms	4 MB
clang++-18	test12.txt	AC	10 ms	4 MB
clang++-18	test13.txt	AC	10 ms	4 MB
clang++-18	test14.txt	AC	10 ms	4 MB
clang++-18	test15.txt	AC	10 ms	4 MB
clang++-18	test16.txt	AC	10 ms	4 MB
clang++-18	test2.txt	AC	5 ms	4 MB
clang++-18	test3.txt	AC	6 ms	4 MB
clang++-18	test4.txt	AC	5 ms	4 MB
clang++-18	test5.txt	AC	5 ms	4 MB
clang++-18	test6.txt	AC	7 ms	4 MB
clang++-18	test7.txt	AC	5 ms	4 MB
clang++-18	test8.txt	AC	5 ms	4 MB
clang++-18	test9.txt	AC	5 ms	4 MB

Back to top page