Submission #1217134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217134		LmaoLmao	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	2 ms	3140 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
#define fi first
#define se second
using namespace std;
 
using ll = long long;
using ii = pair<ll, ll>;
using aa = array<ll,3>; 
 
const int N = 1e6+5;
const int INF = 1e9;
const int mod = 1e9+7;

vector<ii> adj[100005];
ii edge[100005]; 
ll d[100005][2]; 

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{   
    int n=N,m=M,k=K; 
    for(int i=0;i<m;i++) {
        int x=L[i];
        int u=R[i][0],v=R[i][1];
        adj[u].push_back({v,x});
        adj[v].push_back({u,x}); 
        //cout << u << ' ' << v << ' ' << x << endl;
    }
    priority_queue<aa,vector<aa>,greater<aa>> q;
    for(int i=0;i<n;i++) {
        d[i][0]=d[i][1]=1e18;
    }
    for(int i=0;i<k;i++) {
        int x=P[i];
        d[x][0]=0;
        q.push({0,x,0});
    }
    while(!q.empty()) {
        aa u=q.top();
        q.pop();
        if(u[0]>d[u[1]][u[2]] ) continue;
        //cout << u[0] << ' ' << u[1] << ' ' << u[2] << endl;
        for(ii v:adj[u[1]]) {
            if(d[v.fi][1]>v.se+u[0]) {
                d[v.fi][1]=v.se+u[0];
                //cout << d[v.fi][0] << ' '  << d[v.fi][1] << ' '<< v.se << ' ' << v.fi << endl;
                if(d[v.fi][0]>d[v.fi][1]) {
                    swap(d[v.fi][0],d[v.fi][1]);
                }
                //cout << d[v.fi][0] << ' '  << d[v.fi][1] << ' '<< v.se << ' ' << v.fi << endl;
                q.push({d[v.fi][1],v.fi,1});
            }
        }   
        //break;
    }
    return d[0][1];
}

/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

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