oj.uz

Submission #409213

# Submission time Handle Problem Language Result Execution time Memory
409213 2021-05-20T11:12:11 Z Nodir_Bobiev Toll (APIO13_toll) C++17
16 / 100
 1 ms 296 KB 
# include <bits/stdc++.h>
using namespace std;

int n, m, k, A, B, p[15];
vector < vector < int > > graph[15];

int mstWeight;
vector < vector < int > > mstEdges;

void PrimaAlgo(int weight = 0){
    mstWeight = 0;
    mstEdges.clear();
    priority_queue < vector < int > > pq;

    int used[n+1] = {};
    if( weight == 0 ){
        used[1] = true;
        for( auto c: graph[1] )
            pq.push({-c[0], 1, c[1]});
    }else{
        mstWeight = weight;
        used[A] = used[B] = true;
        for( auto c: graph[A] )
            pq.push({-c[0], A, c[1]});
        for( auto c: graph[B] )
            pq.push({-c[0], B, c[1]});
    }

    for( int turn = 2; turn <= n; turn ++ ){
        vector < int > edge;
        while( !pq.empty() ){
            edge = pq.top(); pq.pop();
            if( used[edge[2]] == false )
                break;
        }
        int v = edge[2];
        if( used[v] )
            break;

        edge[0] = -edge[0];
        mstWeight += edge[0];
        mstEdges.push_back(edge);

        used[v] = true;
        for( auto c: graph[v] )
            pq.push({-c[0], v, c[1]});
    }
}

vector < int > simpleGraph[15];
bool vis[15];

void dfs( int v ){
    vis[v] = true;
    for( auto to: simpleGraph[v] )
        if( !vis[to] )
            dfs(to);
}

int main(){
    cin >> n >> m >> k;
    vector < int > weights;
    for( int i = 0; i < m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        weights.push_back(c);
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
    }
    cin >> A >> B;
    for( int i = 1; i <= n; i ++ )
        cin >> p[i];

    PrimaAlgo();
    int minMstWeight = mstWeight;
    long long ans = 0;

    for( auto weight: weights ){
        PrimaAlgo(weight);
        if( minMstWeight >= mstWeight ){
            for( int i = 1; i <= n; i ++ ){
                simpleGraph[i].clear();
                vis[i] = false;
            }
            for( auto edge: mstEdges ){
                simpleGraph[edge[1]].push_back(edge[2]);
                simpleGraph[edge[2]].push_back(edge[1]);
            }
            dfs(1);
            int totalP = 0;
            for( int i = 1; i <= n; i ++ ){
                if( !vis[i] )
                    totalP += p[i];
            }
            ans = max( ans, totalP * 1ll * weight );
        }
    }
    cout << ans;
}
/*
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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 296 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 296 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 296 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 296 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -