oj.uz

Submission #587174

# Submission time Handle Problem Language Result Execution time Memory
587174 2022-07-01T12:34:40 Z MilosMilutinovic Toll (APIO13_toll) C++14
100 / 100
 2169 ms 15892 KB 
/**
 *    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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 253 ms 15804 KB Output is correct
8 Correct 208 ms 15888 KB Output is correct
9 Correct 214 ms 15892 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 253 ms 15804 KB Output is correct
8 Correct 208 ms 15888 KB Output is correct
9 Correct 214 ms 15892 KB Output is correct
10 Correct 1807 ms 15876 KB Output is correct
11 Correct 2164 ms 15848 KB Output is correct
12 Correct 2169 ms 15840 KB Output is correct