Submission #1172696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172696		jadai007	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	2096 ms	320 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

/*#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  my_assert(1==scanf("%d",&solution));
}
*/

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<pair<int, int>> vc[N];
    int dis[N][2];
    for(int i = 0; i < N; ++i) dis[i][0] = dis[i][1] = 1e9 + 7;
    for(int i = 0; i < M; ++i) vc[R[i][0]].emplace_back(R[i][1], L[i]), vc[R[i][1]].emplace_back(R[i][0], L[i]);
    for(int i = 0; i < K; ++i) dis[P[i]][0] = dis[P[i]][1] = 0, pq.emplace(0, P[i]);
    while(!pq.empty()){
        int u = pq.top().second, cnt = pq.top().first;
        if(dis[u][1] < cnt) continue;
        for(auto x:vc[u]){
            int v = x.first, w = x.second;
            if(dis[v][0] > w + cnt){
                if(dis[v][0] < dis[v][1]) pq.emplace(dis[v][0], v);
                dis[v][1] = dis[v][0];
                dis[v][0] = cnt + w;
            }
            else if(dis[v][1] > w + cnt){
                dis[v][1] = w + cnt;
                pq.emplace(dis[v][1], v);
            }
        }
    }
    return dis[0][1];
}
/*
int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}*/

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