oj.uz

Submission #49557

# Submission time Handle Problem Language Result Execution time Memory
49557 2018-05-31T09:09:00 Z doowey Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 710 ms 56948 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 710 ms 56948 KB Output isn't correct
2 Halted 0 ms 0 KB -