Submission #587174

#	Time	Username	Problem	Language	Result	Execution time	Memory
587174		MilosMilutinovic	Toll (APIO13_toll)	C++14	100 / 100	2169 ms	15892 KiB

toll

/**
 *    author:  wxhtzdy
 *    created: 01.07.2022 13:03:09
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(m), b(m), c(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    --a[i]; --b[i];
  }
  vector<int> x(k), y(k);
  for (int i = 0; i < k; i++) {
    cin >> x[i] >> y[i];
    --x[i]; --y[i];
  }
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }
  {
    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return c[i] < c[j];
    });      
    dsu d(n);
    vector<int> na, nb, nc;
    for (int i : order) {
      if (d.unite(a[i], b[i])) {
        na.push_back(a[i]);
        nb.push_back(b[i]);
        nc.push_back(c[i]);
      }
    }
    swap(a, na);
    swap(b, nb);
    swap(c, nc);
    m = (int) a.size();
  }  
  vector<vector<pair<int, int>>> g(n);
  dsu d(n);
  for (int i = 0; i < k; i++) {
    d.unite(x[i], y[i]);    
  }
  vector<array<int, 3>> e;
  for (int i = 0; i < m; i++) {
    if (d.unite(a[i], b[i])) {
      g[a[i]].emplace_back(b[i], c[i]);
      g[b[i]].emplace_back(a[i], c[i]);             
    } else {
      e.push_back({a[i], b[i], c[i]});
    }
  }
  int cc = 0;
  vector<int> comp(n, -1);
  vector<long long> f(n);
  function<void(int, int)> Dfs = [&](int v, int id) {
    comp[v] = id;
    f[id] += p[v];
    for (auto& p : g[v]) {
      if (comp[p.first] == -1) {
        Dfs(p.first, id);
      }
    }
  };
  for (int i = 0; i < n; i++) {
    if (comp[i] == -1) {
      Dfs(i, cc);
      cc += 1;
    }
  }
  for (int i = 0; i < k; i++) {
    x[i] = comp[x[i]];
    y[i] = comp[y[i]];
  }
  for (auto& p : e) {
    p[0] = comp[p[0]];
    p[1] = comp[p[1]];
  }
  long long ans = 0;
  d.p.resize(cc);
  g.resize(cc);
  for (int s = 1; s < (1 << k); s++) {
    for (int i = 0; i < cc; i++) {
      d.p[i] = i;  
    }
    bool ok = true;
    for (int i = 0; i < k; i++) {
      if (s >> i & 1) {
        if (!d.unite(x[i], y[i])) {
          ok = false;
        }
      }
    }
    if (!ok) {
      continue;
    }
    for (int i = 0; i < cc; i++) {
      g[i].clear();
    }
    for (int i = 0; i < k; i++) {
      if (s >> i & 1) {
        g[x[i]].emplace_back(y[i], 1);
        g[y[i]].emplace_back(x[i], 1);
      }
    }
    vector<array<int, 3>> q;       
    for (auto& p : e) {
      if (!d.unite(p[0], p[1])) {
        q.push_back(p);
      } else {
        g[p[0]].emplace_back(p[1], 0);
        g[p[1]].emplace_back(p[0], 0);
      }
    }
    vector<long long> fs(cc);
    vector<bool> spec(cc);
    vector<int> dep(cc);
    vector<int> par(cc);
    Dfs = [&](int v, int pr) {
      fs[v] = f[v];
      dep[v] = dep[pr] + 1;
      par[v] = pr;
      for (auto& p : g[v]) {
        int u = p.first;
        if (u == pr) {
          continue;
        }                
        spec[u] = p.second;
        Dfs(u, v);        
        fs[v] += fs[u];
      }             
    };
    Dfs(0, 0);
    vector<int> mn(cc, 1e9);  
    for (auto& p : q) {
      int u = p[0];
      int v = p[1];
      int w = p[2];          
      if (dep[u] > dep[v]) {
        swap(u, v);
      }
      while (dep[v] > dep[u]) {
        mn[v] = min(mn[v], w);
        v = par[v];
      } 
      while (v != u) {
        mn[v] = min(mn[v], w);
        mn[u] = min(mn[u], w);
        u = par[u];
        v = par[v];
      }
    }
    long long nans = 0;
    for (int i = 1; i < cc; i++) {
      if (spec[i]) {
        nans += fs[i] * mn[i];
      }
    }
    ans = max(ans, nans);
  }
  cout << ans << '\n';
  return 0;
}

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