oj.uz

답안 #511575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
511575 2022-01-16T02:34:13 Z pokmui9909 통행료 (APIO13_toll) C++17
78 / 100
 2500 ms 28024 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
   
#define x first
#define y second
class UnionFind{
public:
    UnionFind(ll S){
        p.resize(S + 5, -1);
    }
    vector<ll> p;
    ll Find(ll n){
      	if(p[n] < 0) return n;
      	else return p[n] = Find(p[n]);
    }
    void Union(ll a, ll b){
        a = Find(a), b = Find(b);
        if (a == b) return;
        p[a] += p[b];
        p[b] = a;
    }
    bool Same(ll a, ll b){ return Find(a) == Find(b); }
private:
};
ll N, M, K;
struct Edge{
    ll u, v, c;
    bool operator<(const Edge &r)const{
        return c < r.c;
    }
};
vector<Edge> E;
vector<Edge> add;
ll P[100005];
UnionFind S(100005);
vector<pair<ll, ll>> G[100005];
ll Par[100005];
ll depth[100005];
ll MinCost[100005];
ll cnt[100005];
vector<Edge> rem;
vector<ll> CG[100005];
vector<Edge> NE;
ll NP[100005];
ll num[100005];
ll check[30][30];
void dfs1(ll n, ll p){
    Par[n] = p;
    for(auto i : G[n]){
        if(i.x == p) continue;
        depth[i.x] = depth[n] + 1;
        dfs1(i.x, n);
    }
}
ll sum = 0, Comps = 0;
void dfs2(ll n, ll p){
    cnt[n] = NP[n];
    for(auto i : G[n]){
        ll nx = i.x, c = i.y;
        if(nx == p) continue;
        dfs2(nx, n);
        cnt[n] += cnt[nx];
        if(c == -1){
            sum += MinCost[nx] * cnt[nx];
        }
    }
}
void dfs3(ll n){
    num[n] = Comps;
    NP[Comps] += P[n];
    for(auto j : CG[n]){
        if(num[j]) continue;
        dfs3(j);
    }
}
 
void init(){
    for(int i = 0; i < 21; i++){
        for(int j = 0; j < 21; j++){
            check[i][j] = 1e18;
        }
    }
    for(int i = 0; i < K; i++){
        ll u = add[i].u, v = add[i].v;
        S.Union(u, v);
    }
    for(int i = 0; i < E.size(); i++){
        ll u = E[i].u, v = E[i].v, c = E[i].c;
        if(S.Same(u, v)){
            rem.push_back({u, v, c});
        } else {
            CG[u].push_back(v);
            CG[v].push_back(u);
            S.Union(u, v);
        }
    }
    for(int i = 1; i <= N; i++){
        if(num[i]) continue;
        Comps++;
        dfs3(i);
    }
    for(int i = 0; i < rem.size(); i++){
        ll u = rem[i].u, v = rem[i].v, c = rem[i].c;
        u = num[u], v = num[v];
        if(u == v) continue;
        if(u > v) swap(u, v);
        check[u][v] = min(check[u][v], c);
    }
    for(int i = 1; i < 21; i++){
        for(int j = i + 1; j < 21; j++){
            if(check[i][j] >= 1e18) continue;
            NE.push_back({i, j, check[i][j]});
        }
    }
    sort(NE.begin(), NE.end());
    E = NE;
    for(int i = 0; i < add.size(); i++){
        add[i].u = num[add[i].u];
        add[i].v = num[add[i].v];
    }
}
 
ll Solve(vector<ll> Plus){
    for(int i = 0; i < 21; i++){
        G[i].clear();
        MinCost[i] = 1e18;
        S.p[i] = -1;
    }
    for(auto i : Plus){
        ll u = add[i].u, v = add[i].v;
        if(S.Same(u, v)) return -1;
        S.Union(u, v);
        G[u].push_back({v, -1});
        G[v].push_back({u, -1});
    }
    for(int i = 0; i < E.size(); i++){
        ll u = E[i].u, v = E[i].v, c = E[i].c;
        if(S.Same(u, v)) continue;
        S.Union(u, v);
        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }
    dfs1(1, -1);
    for(int i = 0; i < E.size(); i++){
        ll u = E[i].u, v = E[i].v, c = E[i].c;
        if(depth[u] < depth[v]) swap(u, v);
        while(depth[u] != depth[v]){
            MinCost[u] = min(MinCost[u], c);
            u = Par[u];
        }
        while(u != v){
            MinCost[u] = min(MinCost[u], c);
            MinCost[v] = min(MinCost[v], c);
            u = Par[u];
            v = Par[v];
        }
    }
    sum = 0;
    dfs2(1, 0);
    return sum;
}
   
int main(){
    cin.tie(0) -> sync_with_stdio(false);
    
    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        ll u, v, c; cin >> u >> v >> c;
        E.push_back({u, v, c});
    }
    for(int i = 1; i <= K; i++){
        ll u, v; cin >> u >> v;
        add.push_back({u, v});
    }
    for(int i = 1; i <= N; i++){
        cin >> P[i];
    }
    sort(E.begin(), E.end());
    init();
    ll ans = 0;
    for(int i = 0; i < (1 << K); i++){
        vector<ll> Plus;
        for(int j = 0; j < K; j++){
            if(i & (1 << j)){
                Plus.push_back(j);
            }
        }
        ans = max(ans, Solve(Plus));
    }
    cout << ans;
}

Compilation message

toll.cpp: In function 'void init()':
toll.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0; i < E.size(); i++){
      |                    ~~^~~~~~~~~~
toll.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0; i < rem.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0; i < add.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp: In function 'll Solve(std::vector<long long int>)':
toll.cpp:137:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int i = 0; i < E.size(); i++){
      |                    ~~^~~~~~~~~~
toll.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i = 0; i < E.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 6 ms 5836 KB Output is correct
5 Correct 13 ms 6100 KB Output is correct
6 Correct 8 ms 6208 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 6 ms 5836 KB Output is correct
5 Correct 13 ms 6100 KB Output is correct
6 Correct 8 ms 6208 KB Output is correct
7 Correct 210 ms 27992 KB Output is correct
8 Correct 241 ms 28024 KB Output is correct
9 Correct 273 ms 28020 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 6 ms 5836 KB Output is correct
5 Correct 13 ms 6100 KB Output is correct
6 Correct 8 ms 6208 KB Output is correct
7 Correct 210 ms 27992 KB Output is correct
8 Correct 241 ms 28024 KB Output is correct
9 Correct 273 ms 28020 KB Output is correct
10 Execution timed out 2584 ms 27968 KB Time limit exceeded
11 Halted 0 ms 0 KB -