Submission #1022271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022271		awu	Toll (APIO13_toll)	C++14	100 / 100	1066 ms	23300 KiB

toll

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
 
#define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(...) [&](decltype(__VA_ARGS__) _x){cerr << #__VA_ARGS__ << " = " << _x << endl; return _x;}(__VA_ARGS__)
using pii = pair<int, int>;
const ll inf = 1ll << 60;
// const int inf = 1 << 30;
 
template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  out << "(" << p.f << ", " << p.s << ")";
  return out;
}
template<typename T>
typename enable_if<!is_same<T, const char *>::value && !is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T o) {
  out << "{";
  int g = o.size();
  for(auto i : o) out << i << (--g ? ", " : "");
  out << "}";
  return out;
}
void my_assert(bool b) {
  if(!b) {
    cerr << "Assertion failed" << endl;
    *((volatile int*)0);
  }
}
#undef assert
#define assert my_assert
 
struct dsu {
  vector<int> p, r;
  bool bad = false;
  vector<int> stac;
  dsu(int n) {
    p.resize(n);
    iota(all(p), 0);
    r.resize(n);
    for(int i = 1; i < n; i++) r[i] = rand();
  }
  int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
  }
  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(r[x] < r[y]) swap(x, y);
    if(x == y) {
      // debug("BAD");
      bad = true;
    }
    p[x] = y;
  }
};
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, k; cin >> n >> m >> k;
  struct edge {
    int a, b, c;
  };
  vector<edge> el(m);
  for(int i = 0; i < m; i++) {
    cin >> el[i].a >> el[i].b >> el[i].c; el[i].a--; el[i].b--;
  }
  sort(all(el), [&](edge a, edge b) {
    return a.c < b.c;
  });
  vector<pii> kl(k);
  for(int i = 0; i < k; i++) {
    cin >> kl[i].f >> kl[i].s; kl[i].f--; kl[i].s--;
  }
  vector<int> p(n);
  for(int i = 0; i < n; i++) {
    cin >> p[i];
  }
  vector<edge> el2;
  dsu uf(n);
  for(auto [a, b, c] : el) {
    if(uf.find(a) != uf.find(b)) {
      uf.merge(a, b);
      el2.push_back({a, b, c});
    }
  }
  uf = dsu(n);
  el = el2;
  el2.clear();
  for(auto [a, b] : kl) {
    uf.merge(a, b);
  }
  vector<edge> el3;
  vector<vector<int>> adj(n);
  for(auto [a, b, c] : el) {
    if(uf.find(a) != uf.find(b)) {
      uf.merge(a, b);
      el2.push_back({a, b, c});
    } else {
      el3.push_back({a, b, c});
    }
  }
  el = el3;
  uf = dsu(n);
  for(auto [a, b, c] : el2) {
    uf.merge(a, b);
  }
  vector<int> cc;
  for(int i = 0; i < n; i++) {
    cc.push_back(uf.find(i));
    if(uf.find(i) != i) {
      p[uf.find(i)] += p[i];
    }
  }
  sort(all(cc));
  cc.erase(unique(all(cc)), cc.end());
  for(int i = 0; i < el.size(); i++) {
    el[i].a = lower_bound(all(cc), uf.find(el[i].a)) - cc.begin();
    el[i].b = lower_bound(all(cc), uf.find(el[i].b)) - cc.begin();
  }
  for(int i = 0; i < kl.size(); i++) {
    kl[i].f = lower_bound(all(cc), uf.find(kl[i].f)) - cc.begin();
    kl[i].s = lower_bound(all(cc), uf.find(kl[i].s)) - cc.begin();
  }
  n = cc.size();
  m = el.size();
  vector<int> p2(n);
  for(int i = 0; i < n; i++) {
    p2[i] = p[cc[i]];
  }
  p = p2;
  int ans = 0;
  for(int msk = 0; msk < 1 << k; msk++) {
    if(k > 15 && __builtin_popcount(msk) < k * 0.6) continue;
    dsu uf(n);
    vector<vector<pii>> adj(n);
    for(int i = 0; i < k; i++) {
      if(msk & (1 << i)) {
        uf.merge(kl[i].f, kl[i].s);
        adj[kl[i].f].push_back({kl[i].s, -1});
        adj[kl[i].s].push_back({kl[i].f, -1});
      }
    }
    if(uf.bad) continue;
    int dc = 0;
    for(int i = 0; i < m; i++) {
      auto [a, b, c] = el[i];
      if(uf.find(a) == uf.find(b)) {
        if(dc == __builtin_popcount(msk)) continue;
        int B = b;
        int C = c;
        function<bool(int, int)> dfs = [&](int cur, int par) {
          if(cur == B) return true;
          for(auto& [i, w] : adj[cur]) {
            if(i == par) continue;
            if(dfs(i, cur)) {
              if(w == -1) {
                dc++;
                w = C;
                for(int j = 0; j < adj[i].size(); j++) {
                  if(adj[i][j].f == cur) {
                    adj[i][j].s = C;
                    break;
                  }
                }
              }
              return true;
            }
          }
          return false;
        };
        dfs(a, -1);
      } else {
        adj[a].push_back({b, 0});
        adj[b].push_back({a, 0});
        uf.merge(a, b);
      }
    }
    int acc = 0;
    function<int(int, int)> dfs = [&](int cur, int par) {
      int ss = p[cur];
      for(auto i : adj[cur]) {
        if(i.f == par) continue;
        int cs = dfs(i.f, cur);
        acc += cs * i.s;
        ss += cs;
      }
      return ss;
    };
    dfs(0, -1);
    ans = max(ans, acc);
  }
  cout << ans << endl;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:87:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |   for(auto [a, b, c] : el) {
      |            ^
toll.cpp:96:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   for(auto [a, b] : kl) {
      |            ^
toll.cpp:101:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |   for(auto [a, b, c] : el) {
      |            ^
toll.cpp:111:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |   for(auto [a, b, c] : el2) {
      |            ^
toll.cpp:123:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<main()::edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int i = 0; i < el.size(); i++) {
      |                  ~~^~~~~~~~~~~
toll.cpp:127:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for(int i = 0; i < kl.size(); i++) {
      |                  ~~^~~~~~~~~~~
toll.cpp:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |       auto [a, b, c] = el[i];
      |            ^
toll.cpp: In lambda function:
toll.cpp:160:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  160 |           for(auto& [i, w] : adj[cur]) {
      |                     ^
toll.cpp:166:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                 for(int j = 0; j < adj[i].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~

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