Submission #208830

#	Time	Username	Problem	Language	Result	Execution time	Memory
208830		IOrtroiii	통행료 (APIO13_toll)	C++14	78 / 100	2539 ms	15492 KiB

toll

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll INF = 1e18;

struct DSU {
   int N;
   vector<int> par;
   DSU(int N = 0) : N(N), par(N) {
      iota(par.begin(), par.end(), 0);
   }
   int getPar(int v) {
      if (v != par[v]) {
         par[v] = getPar(par[v]);
      }
      return par[v];
   }
   bool merge(int v, int u) {
      v = getPar(v);
      u = getPar(u);
      if (v == u) {
         return false;
      } else {
         par[u] = v;
         return true;
      }
   }
};

int main() {
   ios_base::sync_with_stdio(false);
   int N, M, K;
   cin >> N >> M >> K;
   vector<tuple<int, int, int>> edges;
   for (int i = 0; i < M; ++i) {
      int v, u, z;
      cin >> v >> u >> z;
      --v, --u;
      edges.emplace_back(z, v, u);
   }
   vector<pair<int, int>> edges2;
   for (int i = 0; i < K; ++i) {
      int v, u;
      cin >> v >> u;
      --v, --u;
      edges2.emplace_back(v, u);
   }
   vector<ll> A(N);
   for (int i = 0; i < N; ++i) cin >> A[i];
   vector<tuple<int, int, int>> mst;
   {
      DSU d(N);
      sort(edges.begin(), edges.end());
      for (auto e : edges) {
         if (d.merge(get<1>(e), get<2>(e))) {
            mst.emplace_back(e);
         }
      }
   }
   vector<tuple<int, int, int>> maybe;
   vector<tuple<int, int, int>> mustbe;
   {
      DSU d(N);
      for (auto e : edges2) {
         d.merge(e.first, e.second);
      }
      for (auto e : mst) {
         if (d.merge(get<1>(e), get<2>(e))) {
            mustbe.emplace_back(e);
         } else {
            maybe.emplace_back(e);
         }
      }
   }
   int rootId = -1;
   {
      DSU d(N);
      vector<int> roots;
      for (auto e : mustbe) {
         d.merge(get<1>(e), get<2>(e));
      }
      for (int i = 0; i < N; ++i) {
         if (d.par[i] == i) roots.emplace_back(i);
      }
      int newN = roots.size();
      vector<ll> newA(newN);
      vector<int> At(N);
      auto getParId = [&](int v) {
         return lower_bound(roots.begin(), roots.end(), d.getPar(v)) - roots.begin();
      };
      for (int i = 0; i < N; ++i) {
         newA[getParId(i)] += A[i];
         At[i] = getParId(i);
      }
      rootId = getParId(0);
      N = newN;
      A = newA;
      for (auto &e : edges2) {
         e.first = At[e.first];
         e.second = At[e.second];
      }
      for (auto &e : maybe) {
         get<1>(e) = At[get<1>(e)];
         get<2>(e) = At[get<2>(e)];
      }
   }
   auto solve = [&](int mask) {
      vector<vector<int>> adj(N);
      DSU d(N);
      for (int i = 0; i < K; ++i) {
         if (mask & (1 << i)) {
            auto e = edges2[i];
            if (d.merge(e.first, e.second)) {
               adj[e.first].emplace_back(e.second);
               adj[e.second].emplace_back(e.first);
            } else {
               return -INF;
            }
         }
      }
      vector<tuple<int, int, int>> jokes;
      for (auto e : maybe) {
         if (d.merge(get<1>(e), get<2>(e))) {
            adj[get<1>(e)].emplace_back(get<2>(e));
            adj[get<2>(e)].emplace_back(get<1>(e));
         } else {
            jokes.emplace_back(e);
         }
      }
      vector<int> par(N, -1);
      vector<ll> sz(N);
      vector<int> dist(N);
      function<void(int)> Dfs = [&](int v) {
         sz[v] = A[v];
         for (int u : adj[v]) {
            if (u != par[v]) {
               par[u] = v;
               dist[u] = dist[v] + 1;
               Dfs(u);
               sz[v] += sz[u];
            }
         }
      };
      Dfs(rootId);
      vector<ll> val(N, INF);
      for (auto e : jokes) {
         int z, v, u;
         tie(z, v, u) = e;
         if (dist[v] > dist[u]) swap(v, u);
         while (dist[u] > dist[v]) {
            val[u] = min(val[u], ll(z));
            u = par[u];
         }
         while (v != u) {
            val[v] = min(val[v], ll(z));
            val[u] = min(val[u], ll(z));
            v = par[v];
            u = par[u];
         }
      }
      ll tot = 0;
      for (int i = 0; i < K; ++i) {
         if (mask & (1 << i)) {
            int v, u; tie(v, u) = edges2[i];
            if (dist[v] > dist[u]) swap(v, u);
            assert(par[u] == v);
            tot += ll(sz[u]) * val[u];
         }
      }
      return tot;
   };
   ll ans = 0;
   for (int i = 0; i < (1 << K); ++i) ans = max(ans, solve(i));
   cout << ans << "\n";
   return 0;
}

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