oj.uz

Submission #956233

# Submission time Handle Problem Language Result Execution time Memory
956233 2024-04-01T11:24:05 Z Trisanu_Das Toll (APIO13_toll) C++17
100 / 100
 1455 ms 29532 KB 
#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:22:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |     return u == v ? 0 : bool(rt[u] = v);
      |                              ~~~~~~^~~
toll.cpp: In function 'int main()':
toll.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d%d%d", &U[i], &V[i], &W[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d%d", &U[i + m], &V[i + m]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%lld", &P[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20832 KB Output is correct
2 Correct 4 ms 20948 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20832 KB Output is correct
2 Correct 4 ms 20948 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20832 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20832 KB Output is correct
2 Correct 4 ms 20948 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20832 KB Output is correct
5 Correct 6 ms 21036 KB Output is correct
6 Correct 6 ms 20832 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20832 KB Output is correct
2 Correct 4 ms 20948 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20832 KB Output is correct
5 Correct 6 ms 21036 KB Output is correct
6 Correct 6 ms 20832 KB Output is correct
7 Correct 147 ms 29368 KB Output is correct
8 Correct 159 ms 29264 KB Output is correct
9 Correct 154 ms 29276 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20832 KB Output is correct
2 Correct 4 ms 20948 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20832 KB Output is correct
5 Correct 6 ms 21036 KB Output is correct
6 Correct 6 ms 20832 KB Output is correct
7 Correct 147 ms 29368 KB Output is correct
8 Correct 159 ms 29264 KB Output is correct
9 Correct 154 ms 29276 KB Output is correct
10 Correct 881 ms 29464 KB Output is correct
11 Correct 1327 ms 29532 KB Output is correct
12 Correct 1455 ms 29464 KB Output is correct