oj.uz

Submission #409628

# Submission time Handle Problem Language Result Execution time Memory
409628 2021-05-21T08:22:24 Z Nodir_Bobiev Toll (APIO13_toll) C++17
16 / 100
 2 ms 2636 KB 
# include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100;
const int inf = 1e9;

int n, m, k, cnt, pathWeight[30][30], sumP[30], par[30], p[N], comp[N];
bool vis[30];
long long ans;
vector < vector < int > > bridges;
vector < vector < int > > minBridges;
vector < vector < int > > edges;
vector < vector < int > > newEdges;
vector < vector < int > > bridgeEdges;
vector < vector < int > > graph[N];

int get( int x ){
    if( par[x] == x ) return x;
    else return get(par[x]);
}
void unin( int x, int y ){
    x = get(x);
    y = get(y);
    if( x == y ) return ;
    par[x] = y;
}
void dfs( int v ){
    vis[v] = true;
    for( auto edge: bridgeEdges ){
        int c = edge[0], a = edge[1], b = edge[2];
        if( a != v && b != v )
            continue;
        if( !vis[a] ){
            dfs(a);
            sumP[v] += sumP[a];
            ans += 1ll * c * sumP[a];
        }
        else if( !vis[b] ){
            dfs(b);
            sumP[v] += sumP[b];
            ans += 1ll * c * sumP[b];
        }
    }
    for( auto edge: minBridges ){
        int a = edge[1], b = edge[2];
        if( a != v && b != v )
            continue;
        if( !vis[a] )
            dfs(a);
        if( !vis[b] )
            dfs(b);
    }
}

int main(){
    cin >> n >> m >> k;

    for( int i = 0; i < m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
        edges.push_back({c, a, b});
    }

    for( int i = 0; i < k; i ++ ){
        int a, b;
        cin >> a >> b;
        newEdges.push_back({a,b});
        if( !comp[a] ) comp[a] = ++cnt;
        if( !comp[b] ) comp[b] = ++cnt;
    }

    for( int i = 1; i <= n; i ++ )
        cin >> p[i];

    priority_queue < vector < int > > pq;
    for( int i = 1; i <= n; i ++ ){
        if( comp[i] ){
            for( auto to: graph[i] ){
                pq.push({-to[0],i, to[1]});
            }
        }
    }

    while( true ){
        vector < int > edge;
        while( !pq.empty() ){
            edge = pq.top(); pq.pop();
            if( !comp[edge[2]] )
                break;
        }
        if( edge.empty() || comp[edge[2]] )
            break;
        int v = edge[2], from = edge[1];
        comp[v] = comp[from];

        for( auto to: graph[v] ){
            pq.push({-to[0], v, to[1]});
        }
    }

    for( int i = 1; i <= n; i ++ ){
        sumP[comp[i]] += p[i];
    }

    for( int i = 0; i < 30; i ++ ){
        for( int j = 0; j < 30; j ++ ){
            pathWeight[i][j] = inf;
        }
    }

    for( auto edge: edges ){
        int a = edge[1], b = edge[2], c = edge[0];
        pathWeight[comp[a]][comp[b]] = pathWeight[comp[b]][comp[a]] = min(pathWeight[comp[a]][comp[b]], c);
    }

    for( int i = 0; i < 30; i ++ ){
        for( int j = i+1; j < 30; j ++ ){
            if( pathWeight[i][j] != inf )
                bridges.push_back({pathWeight[i][j], i, j});
        }
    }

    sort( bridges.begin(), bridges.end() );

    for( int i = 0; i < 30; i ++ )
        par[i] = i;

    for( auto bridge: bridges ){
        int a = bridge[1], b = bridge[2], c = bridge[0];
        if( get(a) != get(b) ){
            minBridges.push_back(bridge);
            for( auto edge: newEdges ){
                int aa = comp[edge[0]], bb = comp[edge[1]];
                if( (get(a) == get(aa) && get(b) == get(bb)) ||
                        (get(a) == get(bb) && get(b) == get(aa)) ){
                    bridgeEdges.push_back({c, aa, bb});
                    break;
                }
            }
            unin(a, b);
        }
    }
    dfs(comp[1]);
    cout << ans;
/*
    cout << endl;
    cout << cnt << endl;
    for( int i = 1; i <= n; i ++ ){
        cout << comp[i] << ' ';
    }cout << endl;
    for( int i = 1; i <= n; i ++ ){
        cout << depth[i] << ' ';
    }cout << endl;
    for( int i = 1; i <= n; i ++ ){
        cout << sumP[i] << ' ';
    }cout << endl;
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= n; j ++ ){
            cout << pathWeight[i][j] << ' ';
        }cout << endl;
    }
*/
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Incorrect 2 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Incorrect 2 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Incorrect 2 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Incorrect 2 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -