oj.uz

Submission #522932

# Submission time Handle Problem Language Result Execution time Memory
522932 2022-02-06T13:40:24 Z qwerasdfzxcl Toll (APIO13_toll) C++14
78 / 100
 975 ms 54392 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;
Edge X[100]; int pt_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]});
        }
    }
    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(){
    clock_t start = clock();
    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();

    if ((double)(clock()-start) / CLOCKS_PER_SEC >= 0.5) assert(0);

    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;
        }
        pt_x = 0;
        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[pt_x++] = {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 < pt_x; 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:158:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         for(int i = 0; i < NE.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 3724 KB Output is correct
6 Correct 4 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 3 ms 3404 KB Output is correct
5 Correct 4 ms 3724 KB Output is correct
6 Correct 4 ms 3724 KB Output is correct
7 Correct 179 ms 26856 KB Output is correct
8 Correct 250 ms 26836 KB Output is correct
9 Correct 231 ms 26932 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 3 ms 3404 KB Output is correct
5 Correct 4 ms 3724 KB Output is correct
6 Correct 4 ms 3724 KB Output is correct
7 Correct 179 ms 26856 KB Output is correct
8 Correct 250 ms 26836 KB Output is correct
9 Correct 231 ms 26932 KB Output is correct
10 Correct 975 ms 26904 KB Output is correct
11 Runtime error 174 ms 54392 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -