oj.uz

Submission #208843

# Submission time Handle Problem Language Result Execution time Memory
208843 2020-03-12T09:43:13 Z IOrtroiii Toll (APIO13_toll) C++14
100 / 100
 2246 ms 14956 KB 
#include <bits/stdc++.h>

using namespace std;

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

int dist[25];
int par[25];
ll sz[25];
vector<int> adj[25];
int val[25];

namespace DSU {
   int par[100100];
   void init(int N) {
      iota(par, par + N, 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() {
   int N, M, K;
   scanf("%d %d %d", &N, &M, &K);
   vector<tuple<int, int, int>> edges;
   edges.reserve(M);
   for (int i = 0; i < M; ++i) {
      int v, u, z;
      scanf("%d %d %d", &v, &u, &z);
      --v, --u;
      edges.emplace_back(z, v, u);
   }
   vector<pair<int, int>> edges2;
   edges2.reserve(K);
   for (int i = 0; i < K; ++i) {
      int v, u;
      scanf("%d %d", &v, &u);
      --v, --u;
      edges2.emplace_back(v, u);
   }
   vector<ll> A(N);
   for (int i = 0; i < N; ++i) scanf("%I64d", &A[i]);
   vector<tuple<int, int, int>> mst;
   {
      DSU::init(N);
      sort(edges.begin(), edges.end());
      for (auto e : edges) {
         if (DSU::merge(get<1>(e), get<2>(e))) {
            mst.push_back(e);
         }
      }
   }
   vector<tuple<int, int, int>> maybe;
   vector<tuple<int, int, int>> mustbe;
   {
      DSU::init(N);
      for (auto e : edges2) {
         DSU::merge(e.first, e.second);
      }
      for (auto e : mst) {
         if (DSU::merge(get<1>(e), get<2>(e))) {
            mustbe.push_back(e);
         } else {
            maybe.push_back(e);
         }
      }
   }
   int rootId = -1;
   {
      DSU::init(N);
      vector<int> roots;
      for (auto e : mustbe) {
         DSU::merge(get<1>(e), get<2>(e));
      }
      for (int i = 0; i < N; ++i) {
         if (DSU::par[i] == i) roots.push_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(),DSU::getPar(v)) - roots.begin();
      };
      for (int i = 0; i < N; ++i) {
         int id = getParId(i);
         newA[id] += A[i];
         At[i] = id;
      }
      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) {
      for (int i = 0; i < N; ++i) adj[i] = {};
      fill(par, par + N, -1);
      DSU::init(N);
      for (int i = 0; i < K; ++i) {
         if (mask & (1 << i)) {
            auto e = edges2[i];
            if (DSU::merge(e.first, e.second)) {
               adj[e.first].push_back(e.second);
               adj[e.second].push_back(e.first);
            } else {
               return -INF;
            }
         }
      }
      vector<tuple<int, int, int>> jokes;
      for (auto e : maybe) {
         if (DSU::merge(get<1>(e), get<2>(e))) {
            adj[get<1>(e)].push_back(get<2>(e));
            adj[get<2>(e)].push_back(get<1>(e));
         } else {
            jokes.push_back(e);
         }
      }
      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);
      fill(val, 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], z);
            u = par[u];
         }
         while (v != u) {
            val[v] = min(val[v], z);
            val[u] = min(val[u], 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);
            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;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:57:52: warning: format '%d' expects argument of type 'int*', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type* {aka long long int*}' [-Wformat=]
    for (int i = 0; i < N; ++i) scanf("%I64d", &A[i]);
                                                    ^
toll.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &N, &M, &K);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:44:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", &v, &u, &z);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:52:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &v, &u);
       ~~~~~^~~~~~~~~~~~~~~~~
toll.cpp:57:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    for (int i = 0; i < N; ++i) scanf("%I64d", &A[i]);
                                ~~~~~^~~~~~~~~~~~~~~~

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 6 ms 380 KB Output is correct
4 Correct 6 ms 376 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 6 ms 380 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 9 ms 508 KB Output is correct
6 Correct 8 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 6 ms 380 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 9 ms 508 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 281 ms 8944 KB Output is correct
8 Correct 288 ms 8936 KB Output is correct
9 Correct 289 ms 8936 KB Output is correct

Subtask #5
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 6 ms 380 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 9 ms 508 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 281 ms 8944 KB Output is correct
8 Correct 288 ms 8936 KB Output is correct
9 Correct 289 ms 8936 KB Output is correct
10 Correct 1867 ms 8940 KB Output is correct
11 Correct 2236 ms 14956 KB Output is correct
12 Correct 2246 ms 14956 KB Output is correct