oj.uz

답안 #973580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973580 2024-05-02T07:40:07 Z socpite 통행료 (APIO13_toll) C++14
100 / 100
 1063 ms 24772 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e5+5;
const int INF = 1e9;

int n, m, k, cnt, rt;
int up1[maxn], up2[maxn];
int p_real[maxn], p[maxn], id[maxn], dep[maxn], par[maxn], mark[maxn], mn[maxn];
long long dp[maxn];
bool in_tree[maxn];

long long ans = 0;

int Find(int x, int* up){
    return up[x] < 0 ? x : up[x] = Find(up[x], up);
}

bool Union(int a, int b, int* up){
    a = Find(a, up);
    b = Find(b, up);
    if(a == b)return false;
    up[a] += up[b];
    up[b] = a; 
    return true;
}

vector<pair<int, int>> g[maxn];

vector<pair<int, pair<int, int>>> E1, E2, important;
vector<pair<int, int>> fake;

void pre_dfs(int x){
    dp[x] = p_real[x];
    mn[x] = 0;
    for(auto v: g[x]){
        if(v.first == par[x])continue;
        dep[v.first] = dep[x] + 1;
        par[v.first] = x;
        pre_dfs(v.first);
        dp[x] += dp[v.first];
        mark[v.first] = v.second;
    }
}

void solve(int mask){
    for(int i = 1; i <= cnt; i++){
        up1[i] = -1;
        g[i].clear();
    }
    for(int i = 0; i < k; i++){
        if(!(mask&(1<<i)))continue;
        if(!Union(fake[i].first, fake[i].second, up1))return;
        g[fake[i].first].push_back({fake[i].second, 1});
        g[fake[i].second].push_back({fake[i].first, 1});
    }
    for(int i = 0; i < important.size(); i++){
        auto v = important[i];
        in_tree[i] = Union(v.second.first, v.second.second, up1);
        if(in_tree[i]){
            g[v.second.first].push_back({v.second.second, 0});
            g[v.second.second].push_back({v.second.first, 0});
        }
    }
    pre_dfs(rt);
    for(int i = 0; i < important.size(); i++){
        if(in_tree[i])continue;
        int w = important[i].first, a = important[i].second.first, b = important[i].second.second;
        // cout << w << " " << a << " " << b << endl;
        while(a != b){
            if(dep[a] < dep[b])swap(a, b);
            if(!mn[a])mn[a] = w;
            a = par[a];
        }
    }
    long long sum = 0;
    for(int i = 1; i <= cnt; i++){
        // assert(mn[i] > 0 && dp[i] > 0);
        if(mark[i])sum += 1LL*mn[i]*dp[i];
    }
    assert(sum >= 0);
    ans = max(ans, sum);

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    E1.resize(m);
    for(auto &v: E1)cin >> v.second.first >> v.second.second >> v.first;
    sort(E1.begin(), E1.end());
    for(int i = 1; i <= n; i++)up1[i] = -1;
    for(auto v: E1){
        if(Union(v.second.first, v.second.second, up1))E2.push_back(v);
    }    
    fake.resize(k);
    for(auto &v: fake)cin >> v.first >> v.second;
    for(int i = 1 ; i <= n; i++){
        up1[i] = -1;
        cin >> up2[i];
        up2[i] *= -1;
    }
    for(auto v: fake)Union(v.first, v.second, up1);
    for(auto v: E2){
        if(Union(v.second.first, v.second.second, up1))Union(v.second.first, v.second.second, up2);
        else important.push_back(v);
    }
    for(int i = 1; i <= n; i++){
        if(up2[i] < 0){
            cnt++;
            id[i] = cnt;
            p_real[cnt] = -up2[i];
            assert(p_real[cnt] > 0);
        }
    }
    rt = id[Find(1, up2)];
    for(auto &v: fake){
        v.first = id[Find(v.first, up2)];
        v.second = id[Find(v.second, up2)];
        // cout << v.first << " " << v.second << endl;
    }
    for(auto &v: important){
        v.second.first = id[Find(v.second.first, up2)];
        v.second.second = id[Find(v.second.second, up2)];
        // cout << v.second.first << " " << v.second.second << endl;
    }
    for(int i = 1; i < (1<<k); i++)solve(i);
    cout << ans;
}

Compilation message

toll.cpp: In function 'void solve(long long int)':
toll.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < important.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
toll.cpp:68:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < important.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 7004 KB Output is correct
6 Correct 3 ms 7000 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 7004 KB Output is correct
6 Correct 3 ms 7000 KB Output is correct
7 Correct 123 ms 24304 KB Output is correct
8 Correct 129 ms 24256 KB Output is correct
9 Correct 133 ms 24772 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 7004 KB Output is correct
6 Correct 3 ms 7000 KB Output is correct
7 Correct 123 ms 24304 KB Output is correct
8 Correct 129 ms 24256 KB Output is correct
9 Correct 133 ms 24772 KB Output is correct
10 Correct 826 ms 24768 KB Output is correct
11 Correct 1014 ms 24672 KB Output is correct
12 Correct 1063 ms 24256 KB Output is correct