oj.uz

답안 #248423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
248423 2020-07-12T12:30:35 Z receed 통행료 (APIO13_toll) C++14
78 / 100
 2500 ms 36940 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;
vector<pair<int, int>> cg[K];
int p[N], r[N], np[N], par[K], uw[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];
    for (auto &pp : cg[v]) {
        if (pp.first == p)
            continue;
        uw[pp.first] = (pp.second == -1 ? INF : 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, 1 << k) {
        int f = 0;
        rep(j, nn) {
            p[j] = j;
            r[j] = 0;
            cg[j].clear();
        }
        rep(j, k)
            if ((i & (1 << j))) {
                if (!merge(ne[j][1], ne[j][2])) {
                    f = 1;
                    break;
                }
                cg[ne[j][1]].push_back({ne[j][2], -1});
                cg[ne[j][2]].push_back({ne[j][1], -1});
            }
        if (f)
            continue;
        vector<vector<int>> re;
        for (auto &pp : de) {
            if (merge(pp[1], pp[2])) {
                cg[pp[1]].push_back({pp[2], pp[0]});
                cg[pp[2]].push_back({pp[1], pp[0]});
            }
            else
                re.push_back(pp);
        }
        dfs(rt, -1);
        for (auto &pp : re) {
            int v1 = pp[1], v2 = pp[2];
            while (h[v2] > h[v1]) {
                uw[v2] = min(uw[v2], pp[0]);
                v2 = par[v2];
            }
            while (h[v1] > h[v2]) {
                uw[v1] = min(uw[v1], pp[0]);
                v1 = par[v1];
            }
            while (v1 != v2) {
                uw[v1] = min(uw[v1], pp[0]);
                v1 = par[v1];
                uw[v2] = min(uw[v2], pp[0]);
                v2 = par[v2];
            }
        }
        ca = 0;
        rep(j, nn)
            ca += uw[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:113: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:117:5: note: in expansion of macro 'rep'
     rep(i, de.size()) {
     ^~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 4 ms 896 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 338 ms 36864 KB Output is correct
8 Correct 339 ms 36688 KB Output is correct
9 Correct 363 ms 36696 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 338 ms 36864 KB Output is correct
8 Correct 339 ms 36688 KB Output is correct
9 Correct 363 ms 36696 KB Output is correct
10 Correct 2130 ms 36908 KB Output is correct
11 Execution timed out 2561 ms 36940 KB Time limit exceeded
12 Halted 0 ms 0 KB -