oj.uz

Submission #523857

# Submission time Handle Problem Language Result Execution time Memory
523857 2022-02-08T09:38:33 Z pokmui9909 Toll (APIO13_toll) C++17
100 / 100
 1360 ms 25916 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
  
#define x first
#define y second
struct UnionFind{
    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); }
    void Reset() {fill(p.begin(), p.end(), -1);}
};
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[35];
ll depth[35];
ll MinCost[35];
ll cnt[35];
vector<Edge> rem;
vector<pair<ll, ll>> CG[35];
vector<Edge> NE;
vector<Edge> X;
ll NP[35];
ll num[100005];
ll check[30][30];
void dfs1(ll n, ll p){
    Par[n] = p;
    cnt[n] = NP[n];
    for(auto i : CG[n]){
        ll nx = i.x, c = i.y;
        if(nx == p) continue;
        depth[nx] = depth[n] + 1;
        dfs1(i.x, n);
        cnt[n] += cnt[nx];
    }
}
ll sum = 0, Comps = 0;
void dfs3(ll n){
    num[n] = Comps;
    NP[Comps] += P[n];
    for(auto j : G[n]){
        if(num[j.x]) continue;
        dfs3(j.x);
    }
}
  
void init(){
    for(int i = 0; i < 25; i++){
        for(int j = 0; j < 25; j++){
            check[i][j] = 1e10;
        }
    }
  	vector<Edge> MST;
    for(int i = 0; i < M; i++){
        ll u = E[i].u, v = E[i].v, c = E[i].c;
        if(S.Same(u, v)) continue;
        MST.push_back(E[i]);
        S.Union(u, v);
    }
    S.Reset();
    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 < MST.size(); i++){
        ll u = MST[i].u, v = MST[i].v, c = MST[i].c;
        if(S.Same(u, v)){
            rem.push_back({u, v, c});
        } else {
            G[u].push_back({v, c});
            G[v].push_back({u, c});
            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 <= Comps; i++){
        for(int j = i + 1; j <= Comps; j++){
            if(check[i][j] >= 1e10) continue;
            NE.push_back({i, j, check[i][j]});
        }
    }
  	assert(NE.size() <= 130);
    sort(NE.begin(), NE.end());
    for(int i = 0; i < K; i++){
        add[i].u = num[add[i].u];
        add[i].v = num[add[i].v];
    }
}
  
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 bit = 0; bit < (1 << K); bit++){
        for(int i = 0; i < 25; i++){
            CG[i].clear();
            MinCost[i] = 1e10;
            S.p[i] = -1;
        }
        X.clear();
        ll ok = 1;
        for(int i = 0; i < K; i++){
            if(bit == -1 || bit & (1 << i)){
                ll u = add[i].u, v = add[i].v;
                if(S.Same(u, v)){
                    ok = 0;
                    break;
                }
                S.Union(u, v);
                CG[u].push_back({v, -1});
                CG[v].push_back({u, -1});
            }
        }
        if(!ok) continue;
        for(int i = 0; i < NE.size(); i++){
            ll u = NE[i].u, v = NE[i].v, c = NE[i].c;
            if(S.Same(u, v)){
                X.push_back({u, v, c});
                continue;
            }
            S.Union(u, v);
            CG[u].push_back({v, c});
            CG[v].push_back({u, c});
        }
        dfs1(1, -1);
        for(int i = 0; i < X.size(); i++){
            ll u = X[i].u, v = X[i].v, c = X[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;
        for(int i = 0; i < K; i++){
            if(bit & (1 << i)){
                ll u = add[i].u, v = add[i].v;
                if(depth[u] > depth[v]) swap(u, v);
                sum += MinCost[v] * cnt[v];
            }
        }
        ans = max(ans, sum);
    }
    cout << ans;
}

Compilation message

toll.cpp: In function 'void dfs1(ll, ll)':
toll.cpp:52:22: warning: unused variable 'c' [-Wunused-variable]
   52 |         ll nx = i.x, c = i.y;
      |                      ^
toll.cpp: In function 'void init()':
toll.cpp:77:36: warning: unused variable 'c' [-Wunused-variable]
   77 |         ll u = E[i].u, v = E[i].v, c = E[i].c;
      |                                    ^
toll.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i = 0; i < MST.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < rem.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:162:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         for(int i = 0; i < NE.size(); i++){
      |                        ~~^~~~~~~~~~~
toll.cpp:173:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for(int i = 0; i < X.size(); i++){
      |                        ~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 4 ms 3804 KB Output is correct
6 Correct 4 ms 3848 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 4 ms 3804 KB Output is correct
6 Correct 4 ms 3848 KB Output is correct
7 Correct 186 ms 25916 KB Output is correct
8 Correct 188 ms 25880 KB Output is correct
9 Correct 184 ms 25828 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Correct 4 ms 3804 KB Output is correct
6 Correct 4 ms 3848 KB Output is correct
7 Correct 186 ms 25916 KB Output is correct
8 Correct 188 ms 25880 KB Output is correct
9 Correct 184 ms 25828 KB Output is correct
10 Correct 1047 ms 25844 KB Output is correct
11 Correct 1324 ms 25904 KB Output is correct
12 Correct 1360 ms 25884 KB Output is correct