oj.uz

Submission #522944

# Submission time Handle Problem Language Result Execution time Memory
522944 2022-02-06T14:06:29 Z pokmui9909 Toll (APIO13_toll) C++17
78 / 100
 2500 ms 26908 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[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;
        }
    }
    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 < M; 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 {
            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:53:22: warning: unused variable 'c' [-Wunused-variable]
   53 |         ll nx = i.x, c = i.y;
      |                      ^
toll.cpp: In function 'void init()':
toll.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0; i < rem.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:155:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for(int i = 0; i < NE.size(); i++){
      |                        ~~^~~~~~~~~~~
toll.cpp:166:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         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 4 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 4 ms 3404 KB Output is correct
5 Correct 5 ms 3852 KB Output is correct
6 Correct 5 ms 3724 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 4 ms 3404 KB Output is correct
5 Correct 5 ms 3852 KB Output is correct
6 Correct 5 ms 3724 KB Output is correct
7 Correct 206 ms 26832 KB Output is correct
8 Correct 258 ms 26900 KB Output is correct
9 Correct 246 ms 26864 KB Output is correct

Subtask #5
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 4 ms 3404 KB Output is correct
5 Correct 5 ms 3852 KB Output is correct
6 Correct 5 ms 3724 KB Output is correct
7 Correct 206 ms 26832 KB Output is correct
8 Correct 258 ms 26900 KB Output is correct
9 Correct 246 ms 26864 KB Output is correct
10 Correct 1134 ms 26908 KB Output is correct
11 Execution timed out 2601 ms 26848 KB Time limit exceeded
12 Halted 0 ms 0 KB -