oj.uz

Submission #522933

# Submission time Handle Problem Language Result Execution time Memory
522933 2022-02-06T13:41:21 Z qwerasdfzxcl Toll (APIO13_toll) C++14
78 / 100
 1137 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;
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)){
                if (pt_x>=100) return 1;
                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 5 ms 3724 KB Output is correct
6 Correct 7 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 5 ms 3724 KB Output is correct
6 Correct 7 ms 3724 KB Output is correct
7 Correct 194 ms 26832 KB Output is correct
8 Correct 247 ms 26908 KB Output is correct
9 Correct 264 ms 26896 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 5 ms 3724 KB Output is correct
6 Correct 7 ms 3724 KB Output is correct
7 Correct 194 ms 26832 KB Output is correct
8 Correct 247 ms 26908 KB Output is correct
9 Correct 264 ms 26896 KB Output is correct
10 Correct 1137 ms 26884 KB Output is correct
11 Runtime error 188 ms 26904 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -