oj.uz

Submission #29184

# Submission time Handle Problem Language Result Execution time Memory
29184 2017-07-18T15:11:59 Z ozaslan Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 806 ms 161900 KB 
#include<bits/stdc++.h>
#include "crocodile.h"
#define MAX_N 100005
#define oo (1<<30);
using namespace std;



#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>
/*
#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();}

*/
int sonuc = oo;
int kul[MAX_N];
vector< pair<int, int> > E[MAX_N];

int djk(int K, int P[]) {

  priority_queue< pair<int, int> > Q;

  for (int i = 0; i < K; i++) {
    Q.push( make_pair(0, P[i]) );
    kul[P[i]] = 1;
  }

  while (!Q.empty()) {
    int u = Q.top().second;
    int t = -Q.top().first;
    Q.pop();

    if (kul[u] != 1) { kul[u]++; continue; }
    kul[u]++;

    if (u == 0) return t;

    int s = E[u].size();
    for (int i = 0; i < s; i++) {
      int v = E[u][i].first, m = E[u][i].second;

      if (kul[v] <= 1)
        Q.push( make_pair(-(t+m), v) );
    }

  }
  return 365;
}


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{

	for (int i = 0; i < M; i++) {
		E[ R[i][0] ].push_back( make_pair(R[i][1], L[i]) );
		E[ R[i][1] ].push_back( make_pair(R[i][0], L[i]) );
	}

	sonuc = djk(K, P);

  return sonuc;
}
/*
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 main()
{
    freopen("grader.in.2", "r", stdin);
  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
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122412 KB Output is correct
2 Correct 0 ms 122136 KB Output is correct
3 Correct 0 ms 122268 KB Output is correct
4 Correct 6 ms 122564 KB Output is correct
5 Correct 6 ms 122672 KB Output is correct
6 Correct 0 ms 122136 KB Output is correct
7 Correct 3 ms 122268 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 159540 KB Output is correct
2 Correct 119 ms 126888 KB Output is correct
3 Correct 136 ms 128076 KB Output is correct
4 Correct 806 ms 161900 KB Output is correct
5 Correct 496 ms 157400 KB Output is correct
6 Correct 59 ms 124512 KB Output is correct
7 Correct 583 ms 140884 KB Output is correct