oj.uz

Submission #14779

# Submission time Handle Problem Language Result Execution time Memory
14779 2015-06-22T15:16:03 Z minsu Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 591 ms 174420 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<lld,int> ii;
typedef vector<ii> vii;
const int MAXN = 111111;

int block[MAXN];
lld dist[MAXN], dist2[MAXN];
vector<vii> linkd;
priority_queue<ii> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  vector<vii>(N).swap( linkd );
  memset( dist, -1, sizeof dist );
  memset( dist2, -1, sizeof dist2 );
  memset( block, -1, sizeof block );

  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]} ), dist[P[i]]=0;
  while(!pq.empty()){
    int here = pq.top().second; lld d = -pq.top().first; pq.pop();
    if( dist[here] < d ) continue;
    for( auto it : linkd[here] ){
      int there = it.first, co = it.second;
      if( dist[there] == -1 || dist[there] > d + co ){
        dist[there] = d + co;
        block[there] = here;
        pq.push( { -d-co, there } );
      }
    }
  }

  // for(int i=0; i<N; i++) printf("%d ",block[i]);

  for(int i=0; i<K; i++) pq.push( {0, P[i]} ), dist2[P[i]]=0;
  while(!pq.empty()){
    int here = pq.top().second; lld d = -pq.top().first; pq.pop();
    if( dist2[here] < d ) continue;
    for( auto it : linkd[here] ){
      int there = it.first, co = it.second;
      if( block[there] == here ) continue;
      if( dist2[there] == -1 || dist2[there] > d + co ){
        dist2[there] = d + co;
        pq.push( { -d-co, there } );
      }
    }
  }
  return dist2[0];
}

Subtask #1
0.0 / 46.0

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

Subtask #2
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 121540 KB Output is correct
2 Incorrect 0 ms 121276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

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