oj.uz

Submission #426206

# Submission time Handle Problem Language Result Execution time Memory
426206 2021-06-13T15:14:45 Z chirathnirodha Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 665 ms 73012 KB 
//Coded by Chirath Nirodha
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define P push
typedef long long ll;
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  vector<pair<ll,ll> > adj[N];
  for(int i=0;i<M;i++){
    adj[R[i][0]].PB(MP(R[i][1],L[i]));
    adj[R[i][1]].PB(MP(R[i][0],L[i]));
  }
  ll shortest[N][2];
  for(int i=0;i<N;i++){
    shortest[i][0]=10000000000000000;
    shortest[i][1]=10000000000000000;
  }
  priority_queue<pair<ll,ll> > q;
  for(int i=0;i<K;i++){
    shortest[P[i]][0]=0;
    shortest[P[i]][1]=0;
    q.P(MP(0,P[i]));
  }
  while(!q.empty()){
    int c=q.top().S;
    ll val=-q.top().F;
    q.pop();
    if(val>shortest[c][1])continue;
    for(int i=0;i<adj[c].size();i++){
      int a=adj[c][i].F;
      ll len=adj[c][i].S;
	  ll pre=shortest[a][1];
      if(shortest[a][0]>val+len){
        shortest[a][1]=shortest[a][0];
        shortest[a][0]=val+len;
      }
      else if(shortest[a][1]>val+len)shortest[a][1]=val+len;
	  
	  if(shortest[a][1]<pre)q.P(MP(-shortest[a][1],a));
    }
  }
  int ans=shortest[0][1];
  return ans;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<adj[c].size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 492 ms 65296 KB Output is correct
17 Correct 99 ms 14276 KB Output is correct
18 Correct 130 ms 16604 KB Output is correct
19 Correct 665 ms 73012 KB Output is correct
20 Correct 330 ms 52712 KB Output is correct
21 Correct 40 ms 6616 KB Output is correct
22 Correct 356 ms 48288 KB Output is correct