oj.uz

답안 #248460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
248460 2020-07-12T13:22:14 Z receed 통행료 (APIO13_toll) C++14
78 / 100
 2500 ms 37016 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], 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];
    for (auto &pp : cg[v]) {
        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, 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);
        reverse(all(re));
        for (auto &pp : re) {
            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: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 768 KB Output is correct
6 Correct 4 ms 768 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 768 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 317 ms 30416 KB Output is correct
8 Correct 359 ms 30416 KB Output is correct
9 Correct 347 ms 30424 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 768 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 317 ms 30416 KB Output is correct
8 Correct 359 ms 30416 KB Output is correct
9 Correct 347 ms 30424 KB Output is correct
10 Correct 2124 ms 30672 KB Output is correct
11 Correct 2479 ms 37016 KB Output is correct
12 Execution timed out 2505 ms 36948 KB Time limit exceeded