oj.uz

Submission #171012

# Submission time Handle Problem Language Result Execution time Memory
171012 2019-12-27T04:27:56 Z PeppaPig Toll (APIO13_toll) C++14
100 / 100
 2226 ms 16344 KB 
#include <bits/stdc++.h>

#define long long long
#define iii tuple<int, int, int>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;

int dsu[N];

void init() { iota(dsu, dsu + N, 0); }

int find(int x) { return dsu[x] = x == dsu[x] ? x : find(dsu[x]); }

int n, m, k;
long ans;
vector<iii> E, sure, cmp;
vector<pii> toll;
vector<int> g[25];

int cid[N], sz[N];
int par[25], dep[25], weight[25], chk[25];
long csz[25], subsz[25];

void dfs(int u, int p) {
    par[u] = p, dep[u] = dep[p] + 1;
    for(int v : g[u]) if(v != p) {
        dfs(v, u);
        subsz[u] += subsz[v];
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1, a, b, c; i <= m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        E.emplace_back(c, a, b);
    }

    sort(E.begin(), E.end());
    init();
    vector<iii> mst_edge;
    for(iii e : E) {
        int a, b, c; tie(c, a, b) = e;
        if(find(a) != find(b)) {
            dsu[find(a)] = find(b);
            mst_edge.emplace_back(e);
        }
    }
    swap(E, mst_edge);

    init();
    for(int i = 1, a, b; i <= k; i++) {
        scanf("%d %d", &a, &b);
        toll.emplace_back(a, b);
        dsu[find(a)] = find(b);
    }
    for(int i = 1; i <= n; i++) scanf("%d", sz + i);
    for(iii e : E) {
        int a, b, c; tie(c, a, b) = e;
        if(find(a) != find(b)) {
            dsu[find(a)] = find(b);
            sure.emplace_back(e);
        } else cmp.emplace_back(e);
    }

    init();
    for(iii e : sure) {
        int a, b, c; tie(c, a, b) = e;
        dsu[find(a)] = find(b);
    }
    int ptr = 0;
    for(int i = 1; i <= n; i++) if(find(i) == i)
        cid[i] = ++ptr;
    for(int i = 1; i <= n; i++) if(find(i) != i)
        cid[i] = cid[find(i)];
    for(int i = 1; i <= n; i++)
        csz[cid[i]] += sz[i];

    for(int bit = 0; bit < (1 << k); bit++) {
        memset(chk, 0, sizeof chk);
        for(int i = 1; i <= ptr; i++) {
            g[i].clear();
            subsz[i] = csz[i];
            dsu[i] = i;
        }

        bool valid = true;
        for(int i = 0; i < k; i++) if(bit >> i & 1) {
            int a = toll[i].x, b = toll[i].y;
            if(find(cid[a]) == find(cid[b])) {
                valid = false;
                break;
            } else {
                g[cid[a]].emplace_back(cid[b]);
                g[cid[b]].emplace_back(cid[a]);
                dsu[find(cid[a])] = find(cid[b]);
            }
        }
        if(!valid) continue;
        for(int i = 0; i < cmp.size(); i++) {
            int a, b, c; tie(c, a, b) = cmp[i];
            if(find(cid[a]) != find(cid[b])) {
                g[cid[a]].emplace_back(cid[b]);
                g[cid[b]].emplace_back(cid[a]);
                dsu[find(cid[a])] = find(cid[b]);
                chk[i] = true;
            }
        }
        dfs(cid[1], 0);

        for(int i = 0; i < cmp.size(); i++) if(chk[i]) {
            int a, b, c; tie(c, a, b) = cmp[i];
            if(par[cid[b]] == cid[a]) swap(a, b);
            weight[cid[a]] = 0;
        }
        for(int i = 0; i < k; i++) if(bit >> i & 1) {
            int a, b; tie(a, b) = toll[i];
            if(par[cid[b]] == cid[a]) swap(a, b);
            weight[cid[a]] = 1e9;
        }

        for(int i = 0; i < cmp.size(); i++) if(!chk[i]) {
            int a = get<1>(cmp[i]), b = get<2>(cmp[i]), c = get<0>(cmp[i]);
            a = cid[a], b = cid[b];
            if(dep[a] < dep[b]) swap(a, b);

            while(dep[a] > dep[b]) {
                weight[a] = min(weight[a], c);
                a = par[a];
            }
            while(a != b) {
                weight[a] = min(weight[a], c);
                weight[b] = min(weight[b], c);
                a = par[a], b = par[b];
            }
        }

        long ret = 0;
        for(int i = 1; i <= ptr; i++) ret += 1ll * weight[i] * subsz[i];
        ans = max(ans, ret);
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:105:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < cmp.size(); i++) {
                        ~~^~~~~~~~~~~~
toll.cpp:116:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < cmp.size(); i++) if(chk[i]) {
                        ~~^~~~~~~~~~~~
toll.cpp:127:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < cmp.size(); i++) if(!chk[i]) {
                        ~~^~~~~~~~~~~~
toll.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
toll.cpp:62:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", sz + i);
                                 ~~~~~^~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 6 ms 1096 KB Output is correct
6 Correct 5 ms 888 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 6 ms 1096 KB Output is correct
6 Correct 5 ms 888 KB Output is correct
7 Correct 261 ms 16344 KB Output is correct
8 Correct 267 ms 16228 KB Output is correct
9 Correct 266 ms 16228 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 6 ms 1096 KB Output is correct
6 Correct 5 ms 888 KB Output is correct
7 Correct 261 ms 16344 KB Output is correct
8 Correct 267 ms 16228 KB Output is correct
9 Correct 266 ms 16228 KB Output is correct
10 Correct 1964 ms 16208 KB Output is correct
11 Correct 2200 ms 16248 KB Output is correct
12 Correct 2226 ms 16216 KB Output is correct