Submission #49557

#	Time	Username	Problem	Language	Result	Execution time	Memory
49557		doowey	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	710 ms	56948 KiB

crocodile

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

using namespace std;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 9;
vector<pii>T[N];
int dd[N];
bool vv[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  for(int i = 0;i < N;i ++ )
    dd[i] = (int)2e9 + 9,vv[i] = false;
  for(int i = 0;i < M;i ++ ){
    T[R[i][0]].push_back(mp(R[i][1], L[i]));
    T[R[i][1]].push_back(mp(R[i][0], L[i]));
  }
  priority_queue<pii, vector<pii>, greater<pii>> vis;
  vis.push(mp(0,0));
  dd[0] = 0;
  int cur;
  int dis;
  while(!vis.empty()){
    cur = vis.top().fi;
    dis = vis.top().se;
    vis.pop();
    if(vv[cur])
      continue;
    vv[cur] = true;
    for(auto x : T[cur]){
      if(dis + x.se < dd[x.fi]){
        dd[x.fi] = dis + x.se;
        vis.push(mp(x.fi, dd[x.fi]));
      }
    }
  }
  int ans = 0;
  for(int i = 0;i < K;i ++ ){
    ans = max(ans, dd[P[i]] > (int)1e9 ? 0 : dd[P[i]]);
  }
  return ans;
}

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