Submission #1165671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165671		JelalTkm	Toll (APIO13_toll)	C++20	56 / 100	2592 ms	21352 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;

vector<pair<int, int>> bled(K);
vector<pair<int, pair<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];
  }
}

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

  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, pair<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) {
      if (dsu.unite(i.second.first, i.second.second))
        sld.push_back(i);
    }

    for (int i = 0; i < k; i++)
      cin >> bled[i].first >> bled[i].second;

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

    int ans = 0;
    for (int msk = 0; msk < (1 << k); msk++) {
      dsu.init();
      for (int i = 1; i <= n; 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 (!(dsu.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++) {
        state[i] = dsu.unite(sld[i].second.first, sld[i].second.second);
        if (state[i]) {
          auto [u, v] = sld[i].second;
          g[u].push_back(v);
          g[v].push_back(u);
        }
      }

      dfs(1, -1);

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

      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: 0 / 22
• Subtask 5: 0 / 22