제출 #1165698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165698		JelalTkm	통행료 (APIO13_toll)	C++20	100 / 100	1000 ms	23700 KiB

toll

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

class DisjointSets {

  private:
  vector<int> p, sz;

  public:
    DisjointSets(int n) : p(n), sz(n) {
      for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1;}
    }

  int get(int u) {
    return p[u] = (u == p[u] ? u : get(p[u]));
  }

  void init() {
    for (int i = 0; i < (int) p.size(); i++) {
      p[i] = i; sz[i] = 1;
    }
  }

  bool unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v) {
      return 0;
    }
    if (sz[u] < sz[v])
      swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    sz[v] = 0;
    return 1;
  }
  
};

int K = 21, root = 1;

vector<tuple<int, int>> bled(K);
vector<tuple<int, int, int>> sld;
vector<int> a(N), l(N), lvl(N), sub(N), up(N);
vector<vector<int>> g(N, vector<int> ());

void dfs(int u, int p) {
  sub[u] = a[u];
  up[u] = p;
  for (auto v: g[u]) {
    if (v != p) {
      lvl[v] = lvl[u] + 1;
      dfs(v, u);
      sub[u] += sub[v];
    }
  }
}

void upd(int u, int v, int w) {
  while (u != v) {
    if (lvl[u] < lvl[v])
      swap(u, v);
    l[u] = min(l[u], w);
    u = up[u];
  }
}

int n, m, k;
int cnt = 1;

vector<tuple<int, int, int>> simplify(vector<tuple<int, int, int>> edges) {
  DisjointSets dsu(n + 1);
  for (int i = 0; i < k; i++) {
    auto [u, v] = bled[i];
    bool ok = dsu.unite(u, v);
  }

  vector<bool> state((int) edges.size());
  for (int i = 0; i < (int) edges.size(); i++) {
    auto [w, u, v] = edges[i];
    state[i] = dsu.unite(u, v);
  }
  dsu.init();
  for (int i = 0; i < (int) edges.size(); i++) {
    auto [w, u, v] = edges[i];
    if (state[i]) {
      dsu.unite(u, v);
    }
  }

  vector<int> nr(n + 1);
  for (int i = 1; i <= n; i++) {
    int g = dsu.get(i);
    if (nr[g] > 0) continue;
    nr[g] = cnt;
    cnt++;
  }

  // 3 5
  // 1 2
  // 2 4

  vector<tuple<int, int, int>> we;
  for (int i = 0; i < (int) edges.size(); i++) {
    auto [w, u, v] = edges[i];
    if (!state[i]) {
      we.push_back({w, nr[dsu.get(u)], nr[dsu.get(v)]});
    }
  }

  for (int i = 0; i < k; i++) {
    auto [u, v] = bled[i];
    bled[i] = {nr[dsu.get(u)], nr[dsu.get(v)]};
  }

  vector<int> na(n + 1);
  for (int i = 1; i <= n; i++)
    na[nr[dsu.get(i)]] += a[i];

  for (int i = 1; i < cnt; i++)
    a[i] = na[i];

  root = nr[dsu.get(1)];

  return we;
}

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    cin >> n >> m >> k;
    vector<tuple<int, int, int>> edges;
    for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      edges.push_back({w, u, v});
    }

    sort(edges.begin(), edges.end());
    DisjointSets dsu(n + 1);
    for (auto i: edges) {
      auto [w, u, v] = i;
      if (dsu.unite(u, v))
        sld.push_back(i);
    }

    for (int i = 0; i < k; i++) {
      int x, y;
      cin >> x >> y;
      bled[i] = {x, y};
    }

    for (int i = 1; i <= n; i++)
      cin >> a[i];

    sld = simplify(sld);


    int ans = 0;
    DisjointSets dsu1(30);
    for (int msk = 0; msk < (1 << k); msk++) {
      dsu1.init();
      for (int i = 1; i < cnt; i++)
        g[i].clear(), l[i] = INF;
      bool ok = 0;
      for (int i = 0; i < k; i++)
        if (((1 << i) & msk)) {
          auto [u, v] = bled[i];
          if (!(dsu1.unite(u, v))) {
            ok = 1;
            break;
          }
          g[u].push_back(v);
          g[v].push_back(u);
        }
      if (ok) continue;

      vector<bool> state(n + 1);
      for (int i = 0; i < (int) sld.size(); i++) {
        auto [w, u, v] = sld[i];
        state[i] = dsu1.unite(u, v);
        if (state[i]) {
          g[u].push_back(v);
          g[v].push_back(u);
        }
      }

      dfs(root, -1);

      for (int i = 0; i < (int) sld.size(); i++) {
        if (!state[i]) {
          auto [w, u, v] = sld[i];
          upd(u, v, w);
        }
      }

      int sm = 0;
      for (int i = 0; i < k; i++)
        if ((1 << i) & msk) {
          auto [u, v] = bled[i];
          if (lvl[u] > lvl[v])
            swap(u, v);
          sm += l[v] * sub[v];
        }

      ans = max(ans, sm);
    }

    cout << ans << '\n';
  }

  return 0;
}

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