oj.uz

Submission #507916

# Submission time Handle Problem Language Result Execution time Memory
507916 2022-01-13T04:31:45 Z pokmui9909 Toll (APIO13_toll) C++14
56 / 100
 2500 ms 22960 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);
    }
    void reset(){ fill(p.begin(), p.end(), -1); }
    ll Find(ll n){ return (p[n] < 0 ? n : Find(p[n])); }
    void Union(ll a, ll b){
        a = Find(a), b = Find(b);
        if (a == b) return;
        p[b] += p[a];
        p[a] = b;
    }
    bool Same(ll a, ll b){ return Find(a) == Find(b); }
private:
    vector<ll> p;
};
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];
struct MyStruct{
    ll n, c, f;
};
UnionFind S(100005);
vector<pair<ll, ll>> G[100005];
ll Par[100005];
ll depth[100005];
ll MinCost[100005];
ll cnt[100005];
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;
void dfs2(ll n, ll p){
    cnt[n] = P[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];
        }
    }
}

ll Solve(vector<ll> Plus){
    S.reset();
    for(int i = 1; i <= N; i++){
        G[i].clear();
        MinCost[i] = 1e18;
    }
    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 < M; 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 < M; 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());
    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;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 2 ms 3472 KB Output is correct
3 Correct 25 ms 3472 KB Output is correct
4 Correct 27 ms 3480 KB Output is correct
5 Correct 2423 ms 3840 KB Output is correct
6 Correct 1111 ms 3852 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 2 ms 3472 KB Output is correct
3 Correct 25 ms 3472 KB Output is correct
4 Correct 27 ms 3480 KB Output is correct
5 Correct 2423 ms 3840 KB Output is correct
6 Correct 1111 ms 3852 KB Output is correct
7 Execution timed out 2546 ms 22960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 2 ms 3472 KB Output is correct
3 Correct 25 ms 3472 KB Output is correct
4 Correct 27 ms 3480 KB Output is correct
5 Correct 2423 ms 3840 KB Output is correct
6 Correct 1111 ms 3852 KB Output is correct
7 Execution timed out 2546 ms 22960 KB Time limit exceeded
8 Halted 0 ms 0 KB -