Submission #208843

#	Time	Username	Problem	Language	Result	Execution time	Memory
208843		IOrtroiii	Toll (APIO13_toll)	C++14	100 / 100	2246 ms	14956 KiB

toll

#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 (stderr)

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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22