oj.uz

Submission #409595

# Submission time Handle Problem Language Result Execution time Memory
409595 2021-05-21T06:37:54 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], depth[30], p[N], comp[N];
vector < vector < int > > bridges;
vector < vector < int > > minBridges;
vector < vector < int > > edges;
vector < vector < int > > newEdges;
vector < vector < int > > graph[N];

int get( int x ){
    if( par[x] == x ) return x;
    else return par[x] = 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, int f ){
    depth[v] = depth[f] + 1;
    for( auto edge: minBridges ){
        if( edge[1] == v && edge[2] != f ){
            dfs( edge[2], v );
        }
        if( edge[1] != f && edge[2] == v ){
            dfs( edge[1], v );
        }
    }
    sumP[f] += sumP[v];
}

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);
            unin(a, b);
        }
    }
    dfs(comp[1], 0);
    for( int i = 0; i < 30; i ++ ){
        par[i] = i;
    }
    long long ans = 0;
    for( auto bridge: minBridges ){
        int a = bridge[1], b = bridge[2], c = bridge[0];
        if( depth[a] > depth[b] )
            swap( a, b );
        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)) ){
                ans += 1ll * c * sumP[get(b)];
                break;
            }
        }
        unin(a, b);
    }
    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
*/

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:113:43: warning: unused variable 'c' [-Wunused-variable]
  113 |         int a = bridge[1], b = bridge[2], c = bridge[0];
      |                                           ^

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 -