oj.uz

Submission #247663

# Submission time Handle Problem Language Result Execution time Memory
247663 2020-07-11T20:46:11 Z keko37 Toll (APIO13_toll) C++14
100 / 100
 1785 ms 24240 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 300005;

llint n, m, k, cnt, sol;
int a[MAXN], b[MAXN], c[MAXN], na[MAXN], nb[MAXN], in[MAXN], par[MAXN], p[MAXN], dub[MAXN], mn[MAXN], ok[MAXN];
llint cost[MAXN], comp[MAXN], val[MAXN], siz[MAXN];
vector <int> e, rip, v[MAXN];

int nadi (int x) {
    if (x == par[x]) return x;
    return par[x] = nadi(par[x]);
}

bool spoji (int x, int y) {
    x = nadi(x); y = nadi(y);
    par[x] = y;
    return x != y;
}

bool cmp (int e1, int e2) {
    return c[e1] < c[e2];
}

void oboji (int x) {
    if (comp[x] != 0) return;
    comp[x] = cnt;
    val[cnt] += cost[x];
    for (auto sus : v[x]) {
        oboji(sus);
    }
}

void build_graph () {
    sort(in, in + m, cmp);
    for (int i = 1; i <= n; i++) par[i] = i;
    for (int i = 0; i < m; i++) {
        if (spoji(a[in[i]], b[in[i]])) e.push_back(in[i]);
    }

    for (int i = 1; i <= n; i++) par[i] = i;
    for (int i = 0; i < k; i++) spoji(na[i], nb[i]);
    for (auto i : e) {
        if (spoji(a[i], b[i])) {
            v[a[i]].push_back(b[i]);
            v[b[i]].push_back(a[i]);
        } else {
            rip.push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (comp[i] == 0) {
            cnt++;
            oboji(i);
        }
    }

    e = rip;
    for (auto i : e) a[i] = comp[a[i]], b[i] = comp[b[i]];
    for (int i = 0; i < k; i++) na[i] = comp[na[i]], nb[i] = comp[nb[i]];
}

void dfs (int x, int rod) {
    dub[x] = 1 + dub[rod];
    p[x] = rod;
    siz[x] = val[x];
    for (auto sus : v[x]) {
        if (sus == rod) continue;
        dfs(sus, x);
        siz[x] += siz[sus];
    }
}

void lca (int a, int b, int c) {
    if (dub[a] < dub[b]) swap(a, b);
    while (dub[a] > dub[b]) {
        mn[a] = min(mn[a], c);
        a = p[a];
    }
    while (a != b) {
        mn[a] = min(mn[a], c); a = p[a];
        mn[b] = min(mn[b], c); b = p[b];
    }
}

void solve (int mask) {
    for (int i = 1; i <= cnt; i++) {
        par[i] = i;
        mn[i] = 1e9;
        v[i].clear();
    }
    for (int i = 0; i < k; i++) {
        if ((mask & (1 << i)) && spoji(na[i], nb[i])) {
            v[na[i]].push_back(nb[i]);
            v[nb[i]].push_back(na[i]);
            ok[i] = 1;
        } else {
            ok[i] = 0;
        }
    }
    rip.clear();
    for (auto i : e) {
        if (spoji(a[i], b[i])) {
            v[a[i]].push_back(b[i]);
            v[b[i]].push_back(a[i]);
        } else {
            rip.push_back(i);
        }
    }
    dfs(1, 0);
    for (auto i : rip) lca(a[i], b[i], c[i]);
    llint sum = 0;
    for (int i = 0; i < k; i++) {
        if (!ok[i]) continue;
        if (dub[na[i]] < dub[nb[i]]) swap(na[i], nb[i]);
        sum += siz[na[i]] * mn[na[i]];
    }
    sol = max(sol, sum);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        in[i] = i;
    }
    for (int i = 0; i < k; i++) {
        cin >> na[i] >> nb[i];
    }
    for (int i = 1; i <= n; i++) cin >> cost[i];
    build_graph();
    for (int mask = 0; mask < (1 << k); mask++) solve(mask);
    cout << sol;
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 11 ms 7680 KB Output is correct
6 Correct 11 ms 7680 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 11 ms 7680 KB Output is correct
6 Correct 11 ms 7680 KB Output is correct
7 Correct 262 ms 24176 KB Output is correct
8 Correct 264 ms 24052 KB Output is correct
9 Correct 259 ms 24052 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 11 ms 7680 KB Output is correct
6 Correct 11 ms 7680 KB Output is correct
7 Correct 262 ms 24176 KB Output is correct
8 Correct 264 ms 24052 KB Output is correct
9 Correct 259 ms 24052 KB Output is correct
10 Correct 1335 ms 24240 KB Output is correct
11 Correct 1760 ms 24056 KB Output is correct
12 Correct 1785 ms 24180 KB Output is correct