Submission #248463

# Submission time Handle Problem Language Result Execution time Memory
248463 2020-07-12T13:32:40 Z receed Toll (APIO13_toll) C++14
100 / 100
2005 ms 30548 KB
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
 
const int N = 100001, K = 21, INF = 1e7;
pair<int, int> cg[K][K];
int cgs[K];
vector<int> re[K];
int p[N], r[N], np[N], par[K], uw[K], dw[K], cnt[N], h[K];
ll val[K], sum[K];
 
int getp(int v) {
    if (p[v] != v)
        p[v] = getp(p[v]);
    return p[v];
}
 
int merge(int u, int v) {
    u = getp(u);
    v = getp(v);
    if (u == v)
        return 0;
    if (r[u] > r[v])
        p[v] = u;
    else {
        p[u] = v;
        if (r[u] == r[v])
            r[v]++;
    }
    return 1;
}
 
void dfs(int v, int p) {
    par[v] = p;
    sum[v] = val[v];
    rep(i, cgs[v]) {
        auto pp = cg[v][i];
        if (pp.first == p)
            continue;
        dw[pp.first] = (pp.second == -1 ? 1 : 0);
        h[pp.first] = h[v] + 1;
        dfs(pp.first, v);
        sum[v] += sum[pp.first];
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> e(m, vector<int>(3)), ne(k, vector<int>(3, -1)), ce, de;
    rep(i, m) {
        cin >> e[i][1] >> e[i][2] >> e[i][0];
        e[i][1]--; e[i][2]--;
    }
    sort(all(e));
    rep(i, n)
        p[i] = i;
    rep(i, k) {
        cin >> ne[i][1] >> ne[i][2];
        ne[i][1]--;
        ne[i][2]--;
    }
    for (auto &pp : e)
        if (merge(pp[1], pp[2]))
            ne.push_back(pp);
    rep(i, n) {
        p[i] = i;
        r[i] = 0;
    }
    for (auto &pp : ne) {
        if (merge(pp[1], pp[2]) && pp[0] > -1)
            ce.push_back(pp);
        else if (pp[0] > -1)
            de.push_back(pp);
    }
    rep(i, n) {
        p[i] = i;
        r[i] = 0;
    }
    for (auto &pp : ce)
        merge(pp[1], pp[2]);
    vector<int> li;
    rep(i, n)
        li.push_back(getp(i));
    sort(all(li));
    li.resize(unique(all(li)) - li.begin());
    rep(i, n) {
        np[i] = lower_bound(all(li), p[i]) - li.begin();
        cin >> cnt[i];
        val[np[i]] += cnt[i];
    }
    rep(i, ne.size()) {
        ne[i][1] = np[ne[i][1]];
        ne[i][2] = np[ne[i][2]];
    }
    rep(i, de.size()) {
        de[i][1] = np[de[i][1]];
        de[i][2] = np[de[i][2]];
    }
    int nn = li.size(), rt = np[p[0]];
    ll ans = 0, ca;
    rep(i, nn)
        re[i] = vector<int>(3);
    rep(i, 1 << k) {
        int f = 0;
        rep(j, nn) {
            p[j] = j;
            r[j] = 0;
            cgs[j] = 0;
        }
        rep(j, k)
            if ((i & (1 << j))) {
                int v1 = ne[j][1], v2 = ne[j][2];
                if (!merge(v1, v2)) {
                    f = 1;
                    break;
                }
                cg[v1][cgs[v1]++] = {v2, -1};
                cg[v2][cgs[v2]++] = {v1, -1};
            }
        if (f)
            continue;
        int rs = 0;
        for (auto &pp : de) {
            if (merge(pp[1], pp[2])) {
                cg[pp[1]][cgs[pp[1]]++] = {pp[2], pp[0]};
                cg[pp[2]][cgs[pp[2]]++] = {pp[1], pp[0]};
            }
            else
                re[rs++] = pp;
        }
        dfs(rt, -1);
        for (int i = rs - 1; i >= 0; i--) {
            auto pp = re[i];
            int v1 = pp[1], v2 = pp[2];
            while (h[v2] > h[v1]) {
                uw[v2] = pp[0];
                v2 = par[v2];
            }
            while (h[v1] > h[v2]) {
                uw[v1] = pp[0];
                v1 = par[v1];
            }
            while (v1 != v2) {
                uw[v1] = pp[0];
                v1 = par[v1];
                uw[v2] = pp[0];
                v2 = par[v2];
            }
        }
        ca = 0;
        rep(j, nn)
            ca += uw[j] * dw[j] * sum[j];
        ans = max(ans, ca);
    }
    cout << ans;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i = 0; i < (n); i++)
                                     ^
toll.cpp:116:5: note: in expansion of macro 'rep'
     rep(i, ne.size()) {
     ^~~
toll.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i = 0; i < (n); i++)
                                     ^
toll.cpp:120:5: note: in expansion of macro 'rep'
     rep(i, de.size()) {
     ^~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 306 ms 30256 KB Output is correct
8 Correct 320 ms 30288 KB Output is correct
9 Correct 333 ms 30244 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 306 ms 30256 KB Output is correct
8 Correct 320 ms 30288 KB Output is correct
9 Correct 333 ms 30244 KB Output is correct
10 Correct 1524 ms 30420 KB Output is correct
11 Correct 1969 ms 30548 KB Output is correct
12 Correct 2005 ms 30492 KB Output is correct