oj.uz

Submission #47140

# Submission time Handle Problem Language Result Execution time Memory
47140 2018-04-28T01:05:41 Z tmwilliamlin168 Toll (APIO13_toll) C++14
100 / 100
 1410 ms 46292 KB 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 100003;
const int M = 300003;
const int K = 23;

struct Enode {
    int u, v, e;
    bool operator < (const Enode &AA) const {
        return e < AA.e;
    }
} G[M], A[K], New[M], MN[K];
int p[N], Gtot = 0, n, m, k, fa[N], fa2[N], Atot = 0, Newtot = 0, MNtot = 0, tot = 0, remark[N];
ll sp[N];

int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int find2(int x) {return x == fa2[x] ? x : fa2[x] = find2(fa2[x]);}

ll sum[K];
bool used[K], mark[K];
struct node {int nxt, to, w;} E[K * K << 1];
int cnt, point[K], deep[K], fadis[K];
void ins(int u, int v, int w) {E[++cnt] = (node) {point[u], v, w}; point[u] = cnt;}

void dfs(int x) {
    sum[x] = sp[x];
    for (int i = point[x]; i; i = E[i].nxt)
        if (E[i].to != fa[x]) {
            fa[E[i].to] = x;
            fadis[E[i].to] = E[i].w;
            deep[E[i].to] = deep[x] + 1;
            if (E[i].w == 0x7fffffff) mark[E[i].to] = true;
            else mark[E[i].to] = false;
            dfs(E[i].to);
            sum[x] += sum[E[i].to];
        }
}

void minit(int u, int v, int e) {
    if (deep[u] < deep[v]) u ^= v ^= u ^= v;
    while (deep[u] > deep[v]) {
        if (mark[u] && fadis[u] > e)
            fadis[u] = e;
        u = fa[u];
    }
    if (u == v) return;
    while (u != v) {
        if (mark[u] && fadis[u] > e)
            fadis[u] = e;
        if (mark[v] && fadis[v] > e)
            fadis[v] = e;
        u = fa[u]; v = fa[v];
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    int u, v, e, etot = 0;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &e);
        G[++Gtot] = (Enode) {u, v, e};
    }
    stable_sort(G + 1, G + Gtot + 1);
    for (int i = 1; i <= n; ++i) fa[i] = fa2[i] = i;
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d", &u, &v);
        A[++Atot] = (Enode) {u, v, 0};
        u = find(u); v = find(v);
        if (u != v) fa[u] = v, ++etot;
    }
    for (int i = 1; i <= n; ++i) scanf("%d", p + i);
    for (int i = 1; i <= Gtot; ++i) {
        u = find(G[i].u); v = find(G[i].v);
        if (u != v) {
            ++etot;
            fa[u] = v;
            u = find2(G[i].u); v = find2(G[i].v);
            if (u != v) fa2[u] = v;
            if (etot == n - 1) break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!remark[find2(i)])
            remark[fa2[i]] = ++tot;
        remark[i] = remark[fa2[i]];
    }
    for (int i = 1; i <= n; ++i) sp[remark[i]] += p[i];
    for (int i = 1; i <= m; ++i) {
        u = remark[G[i].u]; v = remark[G[i].v];
        if (u != v)
            New[++Newtot] = (Enode) {u, v, G[i].e};
    }
    stable_sort(New + 1, New + Newtot + 1);
    for (int i = 1; i <= k; ++i) A[i].u = remark[A[i].u], A[i].v = remark[A[i].v];
    etot = 0;
    for (int i = 1; i <= tot; ++i) fa[i] = i;
    for (int i = 1; i <= Newtot; ++i) {
        u = find(New[i].u); v = find(New[i].v);
        if (u != v) {
            fa[u] = v;
            ++etot;
            MN[++MNtot] = New[i];
            if (etot == tot - 1) break;
        }
    }
    int S = (1 << k); ll ans = 0;
    for (int s = 1; s < S; ++s) {
        for (int i = 1; i <= tot; ++i) fa[i] = i, point[i] = 0;
        cnt = etot = 0;
        for (int i = 0; i < k; ++i)
            if ((s >> i) & 1) {
                u = A[i + 1].u; v = A[i + 1].v;
                if (find(u) != find(v)) {
                    fa[fa[u]] = fa[v];
                    ++etot;
                    ins(u, v, 0x7fffffff);
                    ins(v, u, 0x7fffffff);
                }
            }
        for (int i = 1; i <= MNtot; ++i) used[i] = false;
        if (etot < tot - 1) {
            for (int i = 1; i <= MNtot; ++i) {
                u = find(MN[i].u); v = find(MN[i].v);
                if (u != v) {
                    used[i] = true;
                    ++etot;
                    fa[u] = v;
                    ins(MN[i].u, MN[i].v, MN[i].e);
                    ins(MN[i].v, MN[i].u, MN[i].e);
                    if (etot == tot - 1) break;
                }
            }
        }
        fa[remark[1]] = 0; dfs(remark[1]);
        for (int i = 1; i <= MNtot; ++i)
            if (!used[i])
                minit(MN[i].u, MN[i].v, MN[i].e);
        ll ret = 0;
        for (int i = 1; i <= tot; ++i)
            if (mark[i])
                ret += sum[i] * fadis[i];
        if (ret > ans) ans = ret;
    }
    printf("%lld\n", ans);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:61: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:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &e);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:75:39: 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", p + i);
                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 3 ms 440 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 812 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 812 KB Output is correct
7 Correct 224 ms 13068 KB Output is correct
8 Correct 233 ms 21448 KB Output is correct
9 Correct 232 ms 27036 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 812 KB Output is correct
7 Correct 224 ms 13068 KB Output is correct
8 Correct 233 ms 21448 KB Output is correct
9 Correct 232 ms 27036 KB Output is correct
10 Correct 1025 ms 31724 KB Output is correct
11 Correct 1391 ms 40004 KB Output is correct
12 Correct 1410 ms 46292 KB Output is correct