test/aoj/2427.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2427

Depends on

• Union-Find (ポテンシャル) (src/DataStructure/UnionFind_Potentialized.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2427
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// ポテンシャルUF
#include <iostream>
#include <vector>
#include <unordered_map>
#include "src/DataStructure/UnionFind_Potentialized.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 long long dist;
 cin >> dist;
 int n;
 cin >> n;
 vector<long long> S(n);
 for (int i= 0; i < n; ++i) cin >> S[i];
 int m;
 cin >> m;
 vector<long long> D(m);
 for (int i= 0; i < m; ++i) cin >> D[i];
 vector<pair<int, int>> ps;
 for (int i= n; i--;)
  for (int j= i; j--;) ps.emplace_back(j, i);
 int N= ps.size();
 long long ans= 1ll << 60;
 vector<long long> diff(N);
 auto dfs= [&](auto &&dfs, int i) -> void {
  if (i == N) {
   UnionFind_Potentialized<long long> uf(n);
   for (int i= N; i--;) {
    auto [a, b]= ps[i];
    if (diff[i] < 0) continue;
    if (!uf.unite(b, a, diff[i])) return;
   }
   vector<long long> s(n), g(n);
   for (int i= n; i--;) s[i]= uf.potential(i), g[i]= s[i] + S[i] * dist;
   for (auto [a, b]: ps) {
    if (!uf.connected(a, b)) return;
    if (uf.diff(b, a) < 1) return;
    if (g[a] > g[b]) {
     bool ok= false;
     for (int k= m; k--;) ok|= s[a] + S[a] * D[k] == s[b] + S[b] * D[k];
     if (!ok) return;
    }
   }
   for (int k= m; k--;) {
    unordered_map<long long, int> memo;
    for (int l= n; l--;) memo[s[l] + S[l] * D[k]]++;
    for (auto [_, cnt]: memo)
     if (cnt > 2) return;
   }
   ans= min(ans, *max_element(g.begin(), g.end()) - s[0]);
   return;
  }
  auto [a, b]= ps[i];
  long long ga= S[a] * dist, gb= S[b] * dist;
  if (gb + 1 >= ga) diff[i]= 1, dfs(dfs, i + 1);
  if (gb + 1 <= ga) diff[i]= ga - gb, dfs(dfs, i + 1);
  if (S[a] > S[b])
   for (int k= m; k--;) diff[i]= (S[a] - S[b]) * D[k], dfs(dfs, i + 1);
  diff[i]= -1, dfs(dfs, i + 1);
 };
 dfs(dfs, 0);
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/2427.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2427
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// ポテンシャルUF
#include <iostream>
#include <vector>
#include <unordered_map>
#line 3 "src/DataStructure/UnionFind_Potentialized.hpp"
#include <algorithm>
#include <cassert>
template <class weight_t> class UnionFind_Potentialized {
 std::vector<int> par;
 std::vector<weight_t> val;
public:
 UnionFind_Potentialized(int n): par(n, -1), val(n) {}
 int leader(int u) {
  if (par[u] < 0) return u;
  int r= leader(par[u]);
  if constexpr (std::is_same_v<weight_t, bool>) val[u]= val[u] ^ val[par[u]];
  else val[u]= val[par[u]] + val[u];
  return par[u]= r;
 }
 //  -p(v) + p(u) = w
 bool unite(int u, int v, weight_t w) {
  int a= leader(u), b= leader(v);
  if constexpr (std::is_same_v<weight_t, bool>) w^= val[u] ^ val[v];
  else w= val[v] + w - val[u];
  if (a == b) return w == weight_t();
  if (par[b] > par[a]) std::swap(a, b), w= -w;
  return par[b]+= par[a], par[a]= b, val[a]= 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) { return leader(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);
 }
};
#line 9 "test/aoj/2427.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 long long dist;
 cin >> dist;
 int n;
 cin >> n;
 vector<long long> S(n);
 for (int i= 0; i < n; ++i) cin >> S[i];
 int m;
 cin >> m;
 vector<long long> D(m);
 for (int i= 0; i < m; ++i) cin >> D[i];
 vector<pair<int, int>> ps;
 for (int i= n; i--;)
  for (int j= i; j--;) ps.emplace_back(j, i);
 int N= ps.size();
 long long ans= 1ll << 60;
 vector<long long> diff(N);
 auto dfs= [&](auto &&dfs, int i) -> void {
  if (i == N) {
   UnionFind_Potentialized<long long> uf(n);
   for (int i= N; i--;) {
    auto [a, b]= ps[i];
    if (diff[i] < 0) continue;
    if (!uf.unite(b, a, diff[i])) return;
   }
   vector<long long> s(n), g(n);
   for (int i= n; i--;) s[i]= uf.potential(i), g[i]= s[i] + S[i] * dist;
   for (auto [a, b]: ps) {
    if (!uf.connected(a, b)) return;
    if (uf.diff(b, a) < 1) return;
    if (g[a] > g[b]) {
     bool ok= false;
     for (int k= m; k--;) ok|= s[a] + S[a] * D[k] == s[b] + S[b] * D[k];
     if (!ok) return;
    }
   }
   for (int k= m; k--;) {
    unordered_map<long long, int> memo;
    for (int l= n; l--;) memo[s[l] + S[l] * D[k]]++;
    for (auto [_, cnt]: memo)
     if (cnt > 2) return;
   }
   ans= min(ans, *max_element(g.begin(), g.end()) - s[0]);
   return;
  }
  auto [a, b]= ps[i];
  long long ga= S[a] * dist, gb= S[b] * dist;
  if (gb + 1 >= ga) diff[i]= 1, dfs(dfs, i + 1);
  if (gb + 1 <= ga) diff[i]= ga - gb, dfs(dfs, i + 1);
  if (S[a] > S[b])
   for (int k= m; k--;) diff[i]= (S[a] - S[b]) * D[k], dfs(dfs, i + 1);
  diff[i]= -1, dfs(dfs, i + 1);
 };
 dfs(dfs, 0);
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	testcase_00	AC	6 ms	4 MB
g++-13	testcase_01	AC	5 ms	4 MB
g++-13	testcase_02	AC	5 ms	4 MB
g++-13	testcase_03	AC	5 ms	4 MB
g++-13	testcase_04	AC	5 ms	4 MB
g++-13	testcase_05	AC	5 ms	4 MB
g++-13	testcase_06	AC	4 ms	4 MB
g++-13	testcase_07	AC	5 ms	3 MB
g++-13	testcase_08	AC	4 ms	4 MB
g++-13	testcase_09	AC	5 ms	4 MB
g++-13	testcase_10	AC	4 ms	4 MB
g++-13	testcase_11	AC	5 ms	4 MB
g++-13	testcase_12	AC	4 ms	4 MB
g++-13	testcase_13	AC	4 ms	4 MB
g++-13	testcase_14	AC	5 ms	4 MB
g++-13	testcase_15	AC	4 ms	4 MB
g++-13	testcase_16	AC	7 ms	4 MB
g++-13	testcase_17	AC	33 ms	4 MB
g++-13	testcase_18	AC	4 ms	3 MB
g++-13	testcase_19	AC	4 ms	4 MB
g++-13	testcase_20	AC	6 ms	4 MB
g++-13	testcase_21	AC	4 ms	3 MB
g++-13	testcase_22	AC	4 ms	3 MB
g++-13	testcase_23	AC	4 ms	4 MB
g++-13	testcase_24	AC	32 ms	4 MB
g++-13	testcase_25	AC	4 ms	4 MB
g++-13	testcase_26	AC	4 ms	4 MB
g++-13	testcase_27	AC	5 ms	4 MB
g++-13	testcase_28	AC	5 ms	4 MB
g++-13	testcase_29	AC	5 ms	4 MB
g++-13	testcase_30	AC	4 ms	4 MB
g++-13	testcase_31	AC	5 ms	4 MB
g++-13	testcase_32	AC	4 ms	4 MB
g++-13	testcase_33	AC	7 ms	4 MB
g++-13	testcase_34	AC	5 ms	4 MB
g++-13	testcase_35	AC	5 ms	4 MB
g++-13	testcase_36	AC	19 ms	4 MB
g++-13	testcase_37	AC	5 ms	4 MB
g++-13	testcase_38	AC	4 ms	4 MB
g++-13	testcase_39	AC	4 ms	4 MB
g++-13	testcase_40	AC	4 ms	4 MB
g++-13	testcase_41	AC	4 ms	4 MB
g++-13	testcase_42	AC	4 ms	4 MB
g++-13	testcase_43	AC	4 ms	4 MB
g++-13	testcase_44	AC	4 ms	4 MB
g++-13	testcase_45	AC	5 ms	4 MB
g++-13	testcase_46	AC	4 ms	3 MB
g++-13	testcase_47	AC	5 ms	4 MB
g++-13	testcase_48	AC	5 ms	4 MB
g++-13	testcase_49	AC	7 ms	4 MB
g++-13	testcase_50	AC	4 ms	4 MB
g++-13	testcase_51	AC	5 ms	4 MB
clang++-18	testcase_00	AC	6 ms	4 MB
clang++-18	testcase_01	AC	5 ms	4 MB
clang++-18	testcase_02	AC	5 ms	4 MB
clang++-18	testcase_03	AC	5 ms	4 MB
clang++-18	testcase_04	AC	5 ms	4 MB
clang++-18	testcase_05	AC	5 ms	4 MB
clang++-18	testcase_06	AC	5 ms	4 MB
clang++-18	testcase_07	AC	5 ms	4 MB
clang++-18	testcase_08	AC	5 ms	4 MB
clang++-18	testcase_09	AC	5 ms	4 MB
clang++-18	testcase_10	AC	4 ms	4 MB
clang++-18	testcase_11	AC	4 ms	4 MB
clang++-18	testcase_12	AC	4 ms	4 MB
clang++-18	testcase_13	AC	4 ms	4 MB
clang++-18	testcase_14	AC	5 ms	4 MB
clang++-18	testcase_15	AC	4 ms	4 MB
clang++-18	testcase_16	AC	7 ms	4 MB
clang++-18	testcase_17	AC	41 ms	4 MB
clang++-18	testcase_18	AC	4 ms	4 MB
clang++-18	testcase_19	AC	4 ms	4 MB
clang++-18	testcase_20	AC	7 ms	4 MB
clang++-18	testcase_21	AC	5 ms	4 MB
clang++-18	testcase_22	AC	5 ms	4 MB
clang++-18	testcase_23	AC	4 ms	4 MB
clang++-18	testcase_24	AC	40 ms	4 MB
clang++-18	testcase_25	AC	5 ms	4 MB
clang++-18	testcase_26	AC	4 ms	4 MB
clang++-18	testcase_27	AC	4 ms	4 MB
clang++-18	testcase_28	AC	5 ms	4 MB
clang++-18	testcase_29	AC	5 ms	4 MB
clang++-18	testcase_30	AC	4 ms	4 MB
clang++-18	testcase_31	AC	4 ms	4 MB
clang++-18	testcase_32	AC	4 ms	4 MB
clang++-18	testcase_33	AC	8 ms	4 MB
clang++-18	testcase_34	AC	5 ms	4 MB
clang++-18	testcase_35	AC	4 ms	4 MB
clang++-18	testcase_36	AC	24 ms	4 MB
clang++-18	testcase_37	AC	5 ms	4 MB
clang++-18	testcase_38	AC	4 ms	4 MB
clang++-18	testcase_39	AC	4 ms	4 MB
clang++-18	testcase_40	AC	4 ms	4 MB
clang++-18	testcase_41	AC	4 ms	4 MB
clang++-18	testcase_42	AC	4 ms	4 MB
clang++-18	testcase_43	AC	4 ms	4 MB
clang++-18	testcase_44	AC	4 ms	4 MB
clang++-18	testcase_45	AC	4 ms	4 MB
clang++-18	testcase_46	AC	4 ms	4 MB
clang++-18	testcase_47	AC	5 ms	4 MB
clang++-18	testcase_48	AC	4 ms	4 MB
clang++-18	testcase_49	AC	8 ms	4 MB
clang++-18	testcase_50	AC	4 ms	4 MB
clang++-18	testcase_51	AC	5 ms	4 MB

Back to top page