oj.uz

답안 #248454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
248454 2020-07-12T13:15:54 Z receed 통행료 (APIO13_toll) C++14
78 / 100
 2500 ms 35512 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, L = 5, INF = 1e7;
vector<pair<int, int>> cg[K], dg[K];
vector<int> td[K], ta[K];
int up[L][K], tin[K], tout[K], ct;
multiset<int> ms[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;
}

int isp(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void dfs(int v, int p) {
    up[0][v] = p;
    tin[v] = ct++;
    sum[v] = val[v];
    for (auto &pp : cg[v]) {
        if (pp.first == p)
            continue;
        h[pp.first] = h[v] + 1;
        uw[pp.first] = (pp.second == -1 ? INF : 0);
        dfs(pp.first, v);
        sum[v] += sum[pp.first];
    }
    tout[v] = ct;
}

void dfs2(int v, int p) {
    for (int i : ta[v])
        ms[v].insert(i);
    for (auto &pp : cg[v]) {
        if (pp.first == p)
            continue;
        dfs2(pp.first, v);
        // if (ms[v].size() < ms[pp.first].size())
        //     swap(ms[v], ms[pp.first]);
        for (int i : ms[pp.first])
            ms[v].insert(i);
    }
    for (int i : td[v]) {
        ms[v].erase(ms[v].find(i));
        ms[v].erase(ms[v].find(i));
    }
    if (uw[v])
        uw[v] = *ms[v].begin();
}

int lca(int u, int v) {
    if (isp(u, v))
        return u;
    for (int i = L - 1; i >= 0; i--)
        if (!isp(up[i][u], v))
            u = up[i][u];
    return up[0][u];
}

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();
            ms[j].clear();
            ta[j].clear();
            td[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);
                // dg[pp[1]].push_back({pp[2], pp[0]});
                // dg[pp[2]].push_back({pp[1], pp[0]});
            }
        }
        ct = 0;
        dfs(rt, rt);
        rep(i, L - 1)
            rep(j, nn)
                up[i + 1][j] = up[i][up[i][j]];
        /*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];
            }
        }*/
        for (auto &pp : re) {
            int l = lca(pp[1], pp[2]);
            ta[pp[1]].push_back(pp[0]);
            ta[pp[2]].push_back(pp[0]);
            td[l].push_back(pp[0]);
            // cout << l << "?\n";
        }
        dfs2(rt, rt);
        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:151: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:155: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 4 ms 384 KB Output is correct
4 Correct 4 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 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 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 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 393 ms 35416 KB Output is correct
8 Correct 483 ms 35492 KB Output is correct
9 Correct 439 ms 35412 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 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 393 ms 35416 KB Output is correct
8 Correct 483 ms 35492 KB Output is correct
9 Correct 439 ms 35412 KB Output is correct
10 Execution timed out 2568 ms 35512 KB Time limit exceeded
11 Halted 0 ms 0 KB -