oj.uz

Submission #667109

# Submission time Handle Problem Language Result Execution time Memory
667109 2022-11-30T11:48:50 Z ansgar Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vb vector<bool>
#define vc vector<char>
#define vvc vector<vc>
#define vvb vector<vb>
#define si set<int>
#define mii map<int,int>

const int mod=1e9+7;
const int N=2e5+1;
const int LN=INT_MAX/10;
struct com{
    bool operator()(pair<pii,int>& a,pair<pii,int>& b){
        return a.second>b.second;
    }
};
struct co{
    bool operator()(pii& a,pii& b){
        return a.second>b.second;
    }
};
int travel_plan(int n,int m,int R[][2],int L[],int k,int P[]){
    vvpii G(n);
    for(int i=0;i<m;i++){
        G[R[i][0]].push_back({R[i][1],L[i]});
        G[R[i][1]].push_back({R[i][0],L[i]});
    }
    priority_queue<pair<pii,int>,vector<pair<pii,int>>,com> Q;
    vi bloq(n,LN);
    for(int i=0;i<k;i++){
        Q.push({{P[i],P[i]},0});
        bloq[P[i]]=0;
    }
    while(Q.size()){
        int u=Q.top().first.first;
        int p=Q.top().first.second;
        int wu=Q.top().second;
        Q.pop();
        if(bloq[u]==LN){
            bloq[u]=p;
            continue;
        }
        for(auto x : G[u]){
            int v=x.first;
            int wv=x.second;
            if(bloq[v]==LN)Q.push({{v,u},wu+wv});
        }
    }
    for(int i=0;i<n;i++){
        //cout<<i<<" "<<bloq[i]<<endl;
    }
    //cout<<endl;
    vi dist(n,LN);
    priority_queue<pii,vpii,co> Q2;
    Q2.push({0,0});
    while(Q2.size()){
        int u=Q2.top().first;
        int wu=Q2.top().second;
        Q2.pop();
        if(dist[u]!=LN)continue;
        //cout<<u<<" "<<wu<<endl;
        dist[u]=wu;
        for(auto x : G[u]){
            int v=x.first;
            int wv=x.second;
            if(bloq[u]==v)continue;
            if(dist[v]==LN)Q2.push({v,wu+wv});
        }
    }
    int sol=LN;
    //cout<<endl;
    for(int i=0;i<k;i++){
        //cout<<P[i]<<" "<<dist[P[i]]<<endl;
        sol=min(sol,dist[P[i]]);
    }
    if(sol==LN)return -1;
    return sol;
}
/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    int R[m][2];
    int L[m];
    for(int i=0;i<m;i++)cin>>R[i][0]>>R[i][1]>>L[i];
    int P[k];
    for(int i=0;i<k;i++)cin>>P[i];
    cout<<travel_plan(n,m,R,L,k,P);
}*/

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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