oj.uz

Submission #351269

# Submission time Handle Problem Language Result Execution time Memory
351269 2021-01-19T19:36:52 Z parsabahrami Toll (APIO13_toll) C++17
78 / 100
 2500 ms 24448 KB 
// When will those clouds all disappear?
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 3e5 + 50, MOD = 1e9 + 7;
int par[N], val[N], H[N], M[N], id[N], rt[N], U[N], V[N], W[N], M2[N], n, m, k;
vector<int> adj[N], vec, roots; ll ret, tot, P[N], S[N];

int Find(int v) {
    return !rt[v] ? v : rt[v] = Find(rt[v]);
}

int Union(int u, int v) {
    u = Find(u), v = Find(v);
    return u == v ? 0 : bool(rt[u] = v);
}

inline void init() {
    fill(rt, rt + N, 0);
}

void DFS(int v, int p = -1) {
    S[v] = P[v];
    for (int i : adj[v]) {
        int u = U[i] ^ V[i] ^ v;
        if (u != p) {
            par[u] = i; 
            H[u] = H[v] + 1;
            DFS(u, v);
            S[v] += S[u];
        }
    }
}

int main() {
    fill(val, val + N, MOD);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &U[i], &V[i], &W[i]);
        id[i] = i;
    }
    sort(id + 1, id + m + 1, [&](int i, int j) {
        return W[i] < W[j];
    });
    for (int i = 1; i <= k; i++) {
        scanf("%d%d", &U[i + m], &V[i + m]);
    }
    for (int i = 1; i <= m; i++) {
        M[i] = Union(U[id[i]], V[id[i]]);
    }
    init();
    for (int i = m + 1; i <= m + k; i++) {
        Union(U[i], V[i]);
    }
    for (int i = 1; i <= m + k; i++) {
        M2[i] = Union(U[id[i]], V[id[i]]);
    }
    init();
    for (int i = 1; i <= m; i++) {
        if (M2[i]) Union(U[id[i]], V[id[i]]);
        if (!M2[i] && M[i]) vec.push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &P[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!rt[i]) roots.push_back(i);
        else P[Find(i)] += P[i];
    }
    for (int i = 1; i <= m + k; i++) U[i] = Find(U[i]), V[i] = Find(V[i]);
    int R = Find(1);
    init(); 
    for (int msk = 1; msk < 1 << k; msk++) {
        for (int v : roots) adj[v] = {}, rt[v] = par[v] = 0;
        int f = 1;
        for (int i = m + 1; i <= m + k; i++) {
            int j = i - m - 1; val[i] = 2e9;
            if (msk & (1 << j)) {
                f &= Union(U[i], V[i]);
                adj[U[i]].push_back(i);
                adj[V[i]].push_back(i);
            }
        }
        if (!f) continue;
        for (int i : vec) {
            if (Union(U[id[i]], V[id[i]])) {
                adj[U[id[i]]].push_back(id[i]);
                adj[V[id[i]]].push_back(id[i]);
            }   
        }
        DFS(R); tot = 0;
        for (int i : vec) {
            int u = U[id[i]], v = V[id[i]], w = W[id[i]];
            while (u != v) {
                if (H[u] < H[v]) val[par[v]] = min(val[par[v]], w), v = U[par[v]] ^ V[par[v]] ^ v;
                else val[par[u]] = min(val[par[u]], w), u = U[par[u]] ^ V[par[u]] ^ u;
            }
        }
        for (int v : roots) {
            if (par[v] > m) tot += 1ll * S[v] * val[par[v]];
        }
        ret = max(ret, tot);
    }
    printf("%lld\n", ret);
    return 0;
}

Compilation message

toll.cpp: In function 'int Union(int, int)':
toll.cpp:23:39: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   23 |     return u == v ? 0 : bool(rt[u] = v);
      |                                       ^
toll.cpp: In function 'int main()':
toll.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d%d%d", &U[i], &V[i], &W[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         scanf("%d%d", &U[i + m], &V[i + m]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |         scanf("%lld", &P[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 8 ms 9836 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 8 ms 9836 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 10 ms 9964 KB Output is correct
6 Correct 9 ms 9984 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 8 ms 9836 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 10 ms 9964 KB Output is correct
6 Correct 9 ms 9984 KB Output is correct
7 Correct 260 ms 17900 KB Output is correct
8 Correct 301 ms 24300 KB Output is correct
9 Correct 284 ms 24448 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 8 ms 9836 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 10 ms 9964 KB Output is correct
6 Correct 9 ms 9984 KB Output is correct
7 Correct 260 ms 17900 KB Output is correct
8 Correct 301 ms 24300 KB Output is correct
9 Correct 284 ms 24448 KB Output is correct
10 Correct 2294 ms 24336 KB Output is correct
11 Execution timed out 2567 ms 24172 KB Time limit exceeded
12 Halted 0 ms 0 KB -