Submission #1155211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155211		raincity	Toll (APIO13_toll)	C++17	100 / 100	778 ms	5384 KiB

toll

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(x) begin(x), end(x)
#define len(x) int((x).size())

template <class T>
inline bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  } else {
    return false;
  }
}

template <class T>
inline bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  } else {
    return false;
  }
}

constexpr int N = 1e5 + 5, M = 3e5 + 5, K = 25;

int n, m, k, rt, sz[N];
ll new_sz[K];
tuple<int, int, int> e_old[M];
pair<int, int> e_new[K];

struct Dsu {
  int f[N], s[N];

  void init(int n) {
    iota(f + 1, f + n + 1, 1);
    fill_n(s + 1, n, 1);
  }

  int fd(int x) {
    while (x != f[x]) x = f[x] = f[f[x]];
    return x;
  }

  bool mg(int x, int y) {
    x = fd(x), y = fd(y);
    if (x == y) {
      return false;
    } else {
      if (s[x] > s[y]) swap(x, y);
      f[x] = y, s[y] += s[x];
      return true;
    }
  }
} dsu;

void simpl() {
  sort(e_old, e_old + m);
  dsu.init(n);
  int new_m = 0;
  for (int i = 0; i < m; ++i) {
    auto [w, u, v] = e_old[i];
    if (dsu.mg(u, v)) e_old[new_m++] = e_old[i];
  }
  m = new_m;
  dsu.init(n);
  for (int i = 0; i < k; ++i) {
    auto [u, v] = e_new[i];
    dsu.mg(u, v);
  }
  static bool essential[N];
  for (int i = 0; i < m; ++i) {
    auto [w, u, v] = e_old[i];
    essential[i] = dsu.mg(u, v);
  }
  dsu.init(n);
  for (int i = 0; i < m; ++i) {
    auto [w, u, v] = e_old[i];
    if (essential[i]) dsu.mg(u, v);
  }
  static int id[N];
  int new_n = 0;
  for (int i = 1; i <= n; ++i) {
    if (dsu.f[i] == i) id[i] = ++new_n;
  }
  for (int i = 1; i <= n; ++i) {
    new_sz[id[dsu.fd(i)]] += sz[i];
  }
  n = new_n;
  new_m = 0;
  for (int i = 0; i < m; ++i) {
    auto [w, u, v] = e_old[i];
    if (!essential[i]) e_old[new_m++] = {w, id[dsu.fd(u)], id[dsu.fd(v)]};
  }
  m = new_m;
  for (int i = 0; i < k; ++i) {
    auto &[u, v] = e_new[i];
    u = id[dsu.fd(u)], v = id[dsu.fd(v)];
  }
  rt = id[dsu.fd(1)];
  // cerr << "n = " << n << "\n";
  // for (int i = 1; i <= n; ++i)
  //   cerr << "new_sz[" << i << "] = " << new_sz[i] << "\n";
  // cerr << "m = " << m << "\n";
  // for (int i = 0; i < m; ++i) {
  //   auto [w, u, v] = e_old[i];
  //   cerr << "e_old[" << i << "] = (" << w << ", " << u << ", " << v <<
  //   ")\n";
  // }
  // cerr << "k = " << k << "\n";
  // for (int i = 0; i < k; ++i) {
  //   auto [u, v] = e_new[i];
  //   cerr << "e_new[" << i << "] = (" << u << ", " << v << ")\n";
  // }
  assert(m == n - 1);
  assert(n <= k + 1);
}

vector<int> adj[K];

void ae(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }

int lim[K], fa[K];
ll sum[K];
int ti, dfn[K];

void dfsInfo(int u, int p) {
  fa[u] = p, sum[u] = new_sz[u];
  dfn[u] = ++ti;
  for (int v : adj[u]) {
    if (v != p) {
      dfsInfo(v, u);
      sum[u] += sum[v];
    }
  }
}

void upd(int u, int v, int w) {
  for (; u != v; u = fa[u]) {
    if (dfn[u] < dfn[v]) swap(u, v);
    chmin(lim[u], w);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin.exceptions(ios::failbit);

  cin >> n >> m >> k;
  for (int i = 0; i < m; ++i) {
    auto &[w, u, v] = e_old[i];
    cin >> u >> v >> w;
  }
  for (int i = 0; i < k; ++i) {
    auto &[u, v] = e_new[i];
    cin >> u >> v;
  }
  for (int i = 1; i <= n; ++i) cin >> sz[i];
  simpl();
  ll ans = 0;
  for (int s = 0; s < (1 << k); ++s) {
    dsu.init(n);
    for (int i = 1; i <= n; ++i) adj[i].clear();
    bool ok = true;
    for (int i = 0; i < k; ++i) {
      if ((s >> i & 1) == 1) {
        auto [u, v] = e_new[i];
        if (!dsu.mg(u, v)) {
          ok = false;
          break;
        }
        ae(u, v);
      }
    }
    if (!ok) continue;
    static bool tree[K];
    for (int i = 0; i < m; ++i) {
      auto [w, u, v] = e_old[i];
      if ((tree[i] = dsu.mg(u, v))) ae(u, v);
    }
    ti = 0;
    dfsInfo(rt, 0);
    memset(lim, 0x3f, sizeof lim);
    for (int i = 0; i < m; ++i) {
      auto [w, u, v] = e_old[i];
      if (!tree[i]) upd(u, v, w);
    }
    ll cur = 0;
    for (int i = 0; i < k; ++i) {
      if ((s >> i & 1) == 1) {
        auto [u, v] = e_new[i];
        if (u == fa[v]) {
          swap(u, v);
        }
        cur += sum[u] * lim[u];
      }
    }
    chmax(ans, cur);
  }
  cout << ans << "\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22