oj.uz

Submission #14781

# Submission time Handle Problem Language Result Execution time Memory
14781 2015-06-23T00:44:36 Z minsu Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 666 ms 171776 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vi;
const int MAXN = 111111;
int visit[MAXN]; vi linkd[MAXN]; priority_queue<ii> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int i=0; i<N; i++) linkd[i].clear();
  memset( visit, 0, sizeof visit);
  for(int i=0; i<M; i++){
    linkd[ R[i][0] ].push_back( { R[i][1], L[i] } );
    linkd[ R[i][1] ].push_back( { R[i][0], L[i] } );
  }
  for(int i=0; i<K; i++) pq.push( { 0, P[i] } ), visit[ P[i] ] = 1;
  while(!pq.empty()){
    int here = pq.top().second, d = -pq.top().first; pq.pop();
    if( ++visit[here] != 2 ) continue;
    if( here == 0 ) return d;
    for(auto it : linkd[here])
      pq.push( { -d-it.second, it.first } );
  }
  return -1;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 122144 KB Output is correct
2 Correct 0 ms 122144 KB Output is correct
3 Correct 0 ms 122144 KB Output is correct
4 Correct 0 ms 122144 KB Output is correct
5 Correct 0 ms 122144 KB Output is correct
6 Correct 2 ms 122144 KB Output is correct
7 Correct 0 ms 122144 KB Output is correct
8 Correct 2 ms 122144 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122408 KB Output is correct
2 Correct 0 ms 122144 KB Output is correct
3 Correct 0 ms 122144 KB Output is correct
4 Correct 4 ms 122760 KB Output is correct
5 Correct 7 ms 122824 KB Output is correct
6 Correct 0 ms 122144 KB Output is correct
7 Correct 0 ms 122144 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 171776 KB Output is correct
2 Correct 101 ms 126764 KB Output is correct
3 Correct 81 ms 127952 KB Output is correct
4 Correct 638 ms 161808 KB Output is correct
5 Correct 412 ms 169612 KB Output is correct
6 Correct 53 ms 124388 KB Output is correct
7 Correct 666 ms 141200 KB Output is correct