oj.uz

Submission #706881

# Submission time Handle Problem Language Result Execution time Memory
706881 2023-03-08T04:25:03 Z DennisTran Toll (APIO13_toll) C++17
78 / 100
 2500 ms 18604 KB 
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define ii pair <int, int>
#define fi first
#define se second
#define int long long
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }

const int MAXN = 3e5 + 5;
const int MAXK = 25;

int N, M, K, c[MAXN], tid[MAXN], tplt = 0, sup[MAXK], h[MAXK], p[MAXK], w[MAXK];
struct Edge{
    int u, v, w;
    friend bool operator < (Edge &A, Edge &B) {
        return A.w < B.w;
    }
} e[MAXN], q[MAXK];


struct DSU{
    int root[MAXN];
    int get(int u) {return root[u] == 0 ? u : root[u] = get(root[u]);}
    bool merge(int u, int v) {
        if ((u = get(u)) == (v = get(v))) return false;
        return root[v] = u, true;
    }
} ds[6];


vector <int> Compress_Edges;
void Make_Tree(void) {
    sort(e + 1, e + M + 1);
    FOR(i, 1, K) ds[2].merge(q[i].u, q[i].v);
    FOR(i, 1, M) if (ds[1].merge(e[i].u, e[i].v)) {
        if (ds[2].merge(e[i].u, e[i].v)) ds[3].merge(e[i].u, e[i].v);
        else Compress_Edges.emplace_back(i);
    }


    FOR(i, 1, N) if (ds[3].get(i) == i)
        tid[i] = ++tplt;

    FOR(i, 1, N) {
        sup[tid[ds[3].get(i)]] += c[i];
    }

    FOR(i, 1, M) {
        e[i].u = tid[ds[3].get(e[i].u)];
        e[i].v = tid[ds[3].get(e[i].v)];
    }

    FOR(i, 1, K) {
        q[i].u = tid[ds[3].get(q[i].u)];
        q[i].v = tid[ds[3].get(q[i].v)];
    }
}


vector <int> ke[MAXK];

void DFS(int u) {
    for (int v : ke[u]) if (v != p[u]) {
        p[v] = u; h[v] = h[u] + 1;
        DFS(v);
    }
}

int DFS_Calc(int u, int now = 0) {
    int res = now * sup[u];
    for (int v : ke[u]) if (v != p[u]) {
        res += DFS_Calc(v, now + w[v]);
    }
    return res;
}

void solve(void) {
    cin >> N >> M >> K;
    FOR(i, 1, M) cin >> e[i].u >> e[i].v >> e[i].w;
    FOR(i, 1, K) cin >> q[i].u >> q[i].v;
    FOR(i, 1, N) cin >> c[i];

    Make_Tree();

    int ans = 0;
    REP(mask, 1 << K) {
        FOR(i, 1, tplt) {
            ke[i].clear();
        }

        FOR(i, 1, N) ds[4].root[i] = ds[5].root[i] = 0;
        FOR(i, 1, K) if ((mask >> i - 1) & 1) {
            if (ds[4].merge(q[i].u, q[i].v)) {
                ke[q[i].u].emplace_back(q[i].v);
                ke[q[i].v].emplace_back(q[i].u);
            }
        }

        deque <Edge> MST_Edges;
        for (int i : Compress_Edges) {
            if (ds[4].merge(e[i].u, e[i].v)) {
                ke[e[i].u].emplace_back(e[i].v);
                ke[e[i].v].emplace_back(e[i].u);
                MST_Edges.push_front({e[i].u, e[i].v, 0});
            } else {
                MST_Edges.push_back(e[i]);
            }
        }

        DFS(tid[ds[3].get(1)]);

        for (auto x : MST_Edges) {
            int u = ds[5].get(x.u), v = ds[5].get(x.v);

            while (u != v) {
                if (h[u] < h[v]) swap(u, v);
                w[u] = x.w;
                ds[5].merge(p[u], u);
                u = ds[5].get(u);
            }
        }

        ans = max(ans, DFS_Calc(tid[ds[3].get(1)]));
    }
    cout << ans;
}

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    file("TASK");
    //int T; cin >> T; while (T--)
    solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message

toll.cpp: In function 'void solve()':
toll.cpp:101:37: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  101 |         FOR(i, 1, K) if ((mask >> i - 1) & 1) {
      |                                   ~~^~~
toll.cpp: In function 'int main()':
toll.cpp:9:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:139:5: note: in expansion of macro 'file'
  139 |     file("TASK");
      |     ^~~~
toll.cpp:9:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:139:5: note: in expansion of macro 'file'
  139 |     file("TASK");
      |     ^~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 3 ms 556 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 1380 ms 17808 KB Output is correct
8 Correct 1409 ms 18604 KB Output is correct
9 Correct 1568 ms 18508 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 1380 ms 17808 KB Output is correct
8 Correct 1409 ms 18604 KB Output is correct
9 Correct 1568 ms 18508 KB Output is correct
10 Execution timed out 2540 ms 18544 KB Time limit exceeded
11 Halted 0 ms 0 KB -