oj.uz

답안 #351271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
351271 2021-01-19T19:43:22 Z parsabahrami 통행료 (APIO13_toll) C++17
78 / 100
 2500 ms 17900 KB 
// When will those clouds all disappear?
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
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] = 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) break;
        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]) {
                  if (w < val[par[v]]) val[par[v]] = w;
                  v = U[par[v]] ^ V[par[v]] ^ v;
                }
                else { 
                  if (w < val[par[u]]) val[par[u]] = w;
                  u = U[par[u]] ^ V[par[u]] ^ u;
                }
            }
        }
        for (int v : roots) {
            if (par[v] > m) tot += S[v] * val[par[v]];
        }
        ret = max(ret, tot);
    }
    printf("%lld\n", ret);
    return 0;
}

Compilation message

toll.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
toll.cpp: In function 'int Union(int, int)':
toll.cpp:24:39: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |     return u == v ? 0 : bool(rt[u] = v);
      |                                       ^
toll.cpp: In function 'int main()':
toll.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |         scanf("%d%d%d", &U[i], &V[i], &W[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         scanf("%d%d", &U[i + m], &V[i + m]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |         scanf("%lld", &P[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct
3 Correct 7 ms 9836 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct
3 Correct 7 ms 9836 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 9 ms 9964 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct
3 Correct 7 ms 9836 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 9 ms 9964 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 249 ms 17900 KB Output is correct
8 Correct 255 ms 17772 KB Output is correct
9 Correct 269 ms 17772 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 6 ms 9856 KB Output is correct
3 Correct 7 ms 9836 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 9 ms 9964 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 249 ms 17900 KB Output is correct
8 Correct 255 ms 17772 KB Output is correct
9 Correct 269 ms 17772 KB Output is correct
10 Correct 2043 ms 17900 KB Output is correct
11 Execution timed out 2531 ms 17900 KB Time limit exceeded
12 Halted 0 ms 0 KB -