Submission #966965

#	Time	Username	Problem	Language	Result	Execution time	Memory
966965		Hugo1729	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	682 ms	79976 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

vector<pair<int,int>> adj[100000];
int visited[100000]={0};

int dp[100000]={0};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for(int i=0;i<K;i++)visited[P[i]]=2;

    priority_queue<pair<int,int>> pq;

    for(int i=0;i<M;i++){
        int v=R[i][0],w=R[i][1];
        if(!(visited[v]==2&&visited[w]==2)){
            if(!(visited[v]==2))swap(v,w);
            if(visited[v])pq.push({-L[i],w});
        }
        adj[R[i][0]].push_back({R[i][1],L[i]});
        adj[R[i][1]].push_back({R[i][0],L[i]});
    }

    while(!pq.empty()){
        int d = -pq.top().first, v = pq.top().second;
        // cout << "s" << v << ' ' << d << '\n';
        pq.pop();

        if(visited[v]==2)continue;
        else if(visited[v]==1){
            visited[v]=2;
            dp[v]=d;
            for(pair<int,int> _ : adj[v]){
                int w=_.first, t=_.second;
                pq.push({-(t+d),w});
                // cout << "a" << w << ' ' << -(t+d) << '\n';
            }
        }else{
            visited[v]=1;
        }
    }


    // cout << pq.top().first;

    // for(int i=0;i<n;i++)cout << dp[i] << ' ';
    // cout << '\n';

    return dp[0];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11