Submission #1217148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217148		LmaoLmao	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	357 ms	82040 KiB

crocodile

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

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

signed travel_plan(signed N, signed M, signed R[][2], signed L[], signed K, signed 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;
        d[x][1]=0;
        q.push({0,x,0});
    }
    while(!q.empty()) {
        aa u=q.top();
        q.pop();
        if(vis[u[1]] ) continue;
        vis[u[1]]=1;
        for(ii v:adj[u[1]]) {
            if(d[v.fi][1]>v.se+u[0]) {
                d[v.fi][1]=v.se+u[0];
                if(d[v.fi][0]>d[v.fi][1]) {
                    swap(d[v.fi][0],d[v.fi][1]);
                }
                q.push({d[v.fi][1],v.fi,1});
            }
        }   
        //break;
    }
    return d[0][1];
}

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