oj.uz

Submission #421878

# Submission time Handle Problem Language Result Execution time Memory
421878 2021-06-09T13:11:00 Z Apiram Toll (APIO13_toll) C++14
0 / 100
 0 ms 204 KB 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>indegree(n,0);
    vector<vector<pair<int,int>>>in(n),out(n);
    for (int i =0;i<m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        out[a].push_back({b,c});
        in[b].push_back({a,c});
        indegree[a]=max(indegree[a],c);
        indegree[b]=max(indegree[b],c);
    }
    vector<pair<int,int>>need;
    for (int i=0;i<k;++i){
        int a,b;
        cin>>a>>b;
        a--,b--;
        need.push_back({a,b});
    }
    vector<int>people(n);
    for (int i =0;i<n;++i){
        cin>>people[i];
    }
    int64_t score=0;
    for (int i =0;i<k;++i){
        int x=need[i].first;
        int y=need[i].second;
        int cost = max(indegree[x],indegree[y]);
        vector<bool>visited(n,false);
        queue<int>q;
        q.push(max(x,y));
        visited[max(x,y)]=true;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for (auto x:out[u]){
                if (!visited[x.first]){
                    visited[x.first]=true;
                    q.push(x.first);
                }
            }
        }
        int ppl = 0;
        for (int i =0;i<n;++i){
            if (visited[i])ppl+=people[i];
        }
        //cout<<cost<<endl;
        score+=ppl*(cost-1);
        
    }
    cout<<score<<endl;
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -