Submission #1022055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022055		awu	Toll (APIO13_toll)	C++14	78 / 100	2531 ms	20464 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;
  vector<bool> bad(1 << k);
  for(int msk = 0; msk < 1 << k; msk++) {
    dsu uf(n);
    for(int i = 0; i < k; i++) {
      if(msk & (1 << i)) {
        uf.merge(kl[i].f, kl[i].s);
      }
    }
    bad[msk] = uf.bad;
  }
  {
    function<void(int, int, vector<vector<int>>)> dfs = [&](int msk, int i, vector<vector<int>> adj) {
      if(i == k) {
        for(int i = 0; i < n; i++) {
          for(auto& w : adj[i]) {
            if(w < 0) w = -w;
            else w = 0;
          }
        }
        int acc = 0;
        function<int(int, int)> dfs = [&](int cur, int par) {
          int ss = p[cur];
          for(int i = 0; i < adj[cur].size(); i++) {
            if(i == par) continue;
            if(adj[cur][i] == inf) continue;
            int cs = dfs(i, cur);
            acc += cs * adj[cur][i];
            ss += cs;
          }
          return ss;
        };
        dfs(0, -1);
        ans = max(ans, acc);
        return;
      }
      {
        int a, b; tie(a, b) = kl[i];
        int mx = 0;
        vector<int> path;
        function<bool(int, int)> dfs = [&](int cur, int par) {
          path.push_back(cur);
          if(cur == b) return true;
          for(int i = 0; i < adj[cur].size(); i++) {
            if(i == par) continue;
            if(adj[cur][i] == -inf) continue;
            if(dfs(i, cur)) {
              mx = max(mx, adj[cur][i]);
              return true;
            }
          }
          path.pop_back();
          return false;
        };
        dfs(a, -1);
        for(int j = 0; j < path.size() - 1; j++) {
          if(adj[path[j]][path[j + 1]] < 0) {
            adj[path[j]][path[j + 1]] = max(adj[path[j]][path[j + 1]], -mx);
            adj[path[j + 1]][path[j]] = max(adj[path[j + 1]][path[j]], -mx);
          }
          if(adj[path[j]][path[j + 1]] == mx) {
            adj[path[j]][path[j + 1]] = -inf;
            adj[path[j + 1]][path[j]] = -inf;
          }
        }
        adj[a][b] = -mx;
        adj[b][a] = -mx;
      }
      for(int j = i + 1; j <= k; j++) {
        dfs(msk ^ (1 << i), j, adj);
      }
    };
    vector<vector<int>> adj(n, vector<int>(n, -inf)); // k edges have negative weight for now
    for(auto [a, b, c] : el) {
      adj[a][b] = adj[b][a] = c;
    }
    for(int i = 0; i < k; i++) {
      dfs(0, i, adj);
    }
  }
  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: In lambda function:
toll.cpp:161:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |           for(int i = 0; i < adj[cur].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~~
toll.cpp: In lambda function:
toll.cpp:181:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |           for(int i = 0; i < adj[cur].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~~
toll.cpp: In lambda function:
toll.cpp:193:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |         for(int j = 0; j < path.size() - 1; j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:211:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  211 |     for(auto [a, b, c] : el) {
      |              ^

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