oj.uz

Submission #208830

# Submission time Handle Problem Language Result Execution time Memory
208830 2020-03-12T09:22:39 Z IOrtroiii Toll (APIO13_toll) C++14
78 / 100
 2500 ms 15492 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 7 ms 380 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 7 ms 380 KB Output is correct
5 Correct 11 ms 620 KB Output is correct
6 Correct 9 ms 504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 7 ms 380 KB Output is correct
5 Correct 11 ms 620 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 282 ms 15492 KB Output is correct
8 Correct 302 ms 15320 KB Output is correct
9 Correct 296 ms 15320 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 7 ms 380 KB Output is correct
5 Correct 11 ms 620 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 282 ms 15492 KB Output is correct
8 Correct 302 ms 15320 KB Output is correct
9 Correct 296 ms 15320 KB Output is correct
10 Execution timed out 2539 ms 15320 KB Time limit exceeded
11 Halted 0 ms 0 KB -