oj.uz

Submission #561989

# Submission time Handle Problem Language Result Execution time Memory
561989 2022-05-14T03:17:38 Z hoanghq2004 Toll (APIO13_toll) C++14
100 / 100
 1797 ms 14232 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 10;

int n, m, k;
int comp[N];
int par[N], sz[N], root[N];
vector <pair <int, int> > g[N];
int d[N], cap[N];
long long tot[N], a[N];

int Find(int u) {
    return (u == root[u] ? u : root[u] = Find(root[u]));
}

int Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return 0;
    if (sz[u] < sz[v]) swap(u, v);
    root[v] = u;
    sz[u] += sz[v];
    return 1;
}

void dfs(int u, int p) {
    assert(comp[u] == 0);
    comp[u] = m;
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

void get(int u, int p) {
    tot[u] = a[u];
    for (auto [v, w]: g[u]) {
        if (v == p) continue;
        d[v] = d[u] + 1;
        par[v] = u;
        get(v, u);
        tot[u] += tot[v];
    }
}

int main() {
//    freopen("toll.inp", "r", stdin);
//    freopen("toll.ans", "w", stdout);
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    vector <tuple <int, int, int> > e, ne;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back({w, u, v});
    }
    sort(e.begin(), e.end());
    vector <pair <int, int> > add;
    for (int i = 1; i <= n; ++i) root[i] = i, sz[i] = 1;
    while (k--) {
        int u, v;
        cin >> u >> v;
        Union(u, v);
        add.push_back({u, v});
    }
    for (auto [w, u, v]: e) {
        if (Union(u, v)) g[u].push_back({v, 0}), g[v].push_back({u, 0});
    }
    m = 0;
    for (int i = 1; i <= n; ++i) {
        if (!comp[i]) {
            ++m;
            dfs(i, 0);
        }
    }
//    assert(m <= 20);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        a[comp[i]] += x;
    }
    n = m;
    for (int i = 1; i <= n; ++i) root[i] = i, sz[i] = 1;
    for (auto &[u, v]: add) u = comp[u], v = comp[v];
    for (auto &[w, u, v]: e) {
        u = comp[u], v = comp[v];
        if (Union(u, v)) ne.push_back({w, u, v});
    }
    for (int i = 1; i <= n; ++i) g[i].clear();
    swap(e, ne);
//    cout << m << '\n';
    long long ans = 0;
    for (int mask = 0; mask < (1 << add.size()); ++mask) {
        for (int i = 1; i <= n; ++i) root[i] = i, sz[i] = 1, g[i].clear();
        int ok = 1;
        for (int i = 0; i < add.size(); ++i) {
            if (mask >> i & 1) {
                if (Union(add[i].first, add[i].second)) {
                    g[add[i].first].push_back({add[i].second, 1});
                    g[add[i].second].push_back({add[i].first, 1});
                } else {
                    ok = 0;
                    break;
                }
            }
        }
        if (ok == 0) continue;
        vector <tuple <int, int, int> > rem;
        for (auto [w, u, v]: e) {
            if (Union(u, v)) {
                g[u].push_back({v, 0});
                g[v].push_back({u, 0});
            } else rem.push_back({w, u, v});
        }
        get(comp[1], 0);
        for (int i = 1; i <= n; ++i) cap[i] = 1e9;
        for (auto [w, u, v]: rem) {
            while (u != v) {
                if (d[u] < d[v]) swap(u, v);
                cap[u] = min(cap[u], w);
                u = par[u];
            }
        }
        long long cur = 0;
        for (int u = 1; u <= n; ++u)
            for (auto [v, type]: g[u]) {
                if (type && par[u] == v) assert(cap[u] < 1e9), cur += tot[u] * cap[u];
            }
        ans = max(ans, cur);
    }
//    cerr << ans;
    cout << ans;
}

Compilation message

toll.cpp: In function 'void dfs(int, int)':
toll.cpp:37:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for (auto [v, w]: g[u]) {
      |               ^
toll.cpp: In function 'void get(int, int)':
toll.cpp:45:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for (auto [v, w]: g[u]) {
      |               ^
toll.cpp: In function 'int main()':
toll.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for (auto [w, u, v]: e) {
      |               ^
toll.cpp:92:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for (auto &[u, v]: add) u = comp[u], v = comp[v];
      |                ^
toll.cpp:93:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |     for (auto &[w, u, v]: e) {
      |                ^
toll.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int i = 0; i < add.size(); ++i) {
      |                         ~~^~~~~~~~~~~~
toll.cpp:117:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |         for (auto [w, u, v]: e) {
      |                   ^
toll.cpp:125:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |         for (auto [w, u, v]: rem) {
      |                   ^
toll.cpp:134:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |             for (auto [v, type]: g[u]) {
      |                       ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 3 ms 2656 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 3 ms 2656 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 4 ms 2948 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 3 ms 2656 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 4 ms 2948 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 191 ms 14232 KB Output is correct
8 Correct 212 ms 14160 KB Output is correct
9 Correct 192 ms 14132 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 3 ms 2656 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 4 ms 2948 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 191 ms 14232 KB Output is correct
8 Correct 212 ms 14160 KB Output is correct
9 Correct 192 ms 14132 KB Output is correct
10 Correct 1337 ms 14168 KB Output is correct
11 Correct 1784 ms 13740 KB Output is correct
12 Correct 1797 ms 12348 KB Output is correct