oj.uz

Submission #70016

# Submission time Handle Problem Language Result Execution time Memory
70016 2018-08-22T09:09:18 Z nvmdava Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1904 ms 102652 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

struct Chamber{
	int cost, id, from;
	Chamber(int from, int id, int cost){
		this -> from = from;
		this -> id = id;
		this -> cost = cost;
	}
	
	bool operator<(const Chamber& rhs) const {
		return cost > rhs.cost;
	}
};

struct Path{
	int to, cost;
	Path(int to, int cost){
		this -> to = to;
		this -> cost = cost;
	}
};

priority_queue<Chamber> pq;
vector<Path> p[100001];
int block[100001];
int ans[100001];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(int i = 0; i < M ; i++){
		p[R[i][0]].push_back(Path(R[i][1], L[i]));
		p[R[i][1]].push_back(Path(R[i][0], L[i]));
	}
	memset(ans, -1, sizeof(ans));
	for(int i = 0; i < K; i++){
		pq.push(Chamber(-2, P[i], 0));
		ans[P[i]] = -2;
		block[P[i]] = -1;
	}
	int v;
	while(!pq.empty()){
		v = pq.top().id;
		if(ans[v] >= 0){
			pq.pop();
			continue;
		}
		
		if(ans[v] == -1){
			ans[v] = -2;
			block[v] = pq.top().from;
			pq.pop();
			continue;
		}
		
		if(block[v] == pq.top().from){
			pq.pop();
			continue;
		}
		
		ans[v] = pq.top().cost;
		
		for(auto x : p[v]){
			if(ans[x.to] >= 0) continue;
			pq.push(Chamber(v, x.to, ans[v] + x.cost));
		}
	}
	
	memset(ans, -1, sizeof(ans));
	pq.push(Chamber(0, 0, 0));
	while(!pq.empty()){
		v = pq.top().id;
		if(ans[v] != -1){
			pq.pop();
			continue;
		}
		ans[v] = pq.top().cost;
		if(block[v] == -1){
			return ans[v];
		}
		for(auto x : p[v]){
			if(x.to == block[v]) continue;
			if(ans[x.to] != -1) continue;
			pq.push(Chamber(0, x.to, ans[v] + x.cost));
		}
	}
}

/*
#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();}

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()
{
  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;
}
*/

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 6 ms 3176 KB Output is correct
3 Correct 6 ms 3176 KB Output is correct
4 Correct 6 ms 3268 KB Output is correct
5 Correct 5 ms 3340 KB Output is correct
6 Correct 6 ms 3356 KB Output is correct
7 Correct 7 ms 3604 KB Output is correct
8 Correct 6 ms 3720 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 6 ms 3176 KB Output is correct
3 Correct 6 ms 3176 KB Output is correct
4 Correct 6 ms 3268 KB Output is correct
5 Correct 5 ms 3340 KB Output is correct
6 Correct 6 ms 3356 KB Output is correct
7 Correct 7 ms 3604 KB Output is correct
8 Correct 6 ms 3720 KB Output is correct
9 Correct 9 ms 3940 KB Output is correct
10 Correct 5 ms 3940 KB Output is correct
11 Correct 7 ms 3940 KB Output is correct
12 Correct 12 ms 4420 KB Output is correct
13 Correct 10 ms 4536 KB Output is correct
14 Correct 5 ms 4536 KB Output is correct
15 Correct 6 ms 4536 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 6 ms 3176 KB Output is correct
3 Correct 6 ms 3176 KB Output is correct
4 Correct 6 ms 3268 KB Output is correct
5 Correct 5 ms 3340 KB Output is correct
6 Correct 6 ms 3356 KB Output is correct
7 Correct 7 ms 3604 KB Output is correct
8 Correct 6 ms 3720 KB Output is correct
9 Correct 9 ms 3940 KB Output is correct
10 Correct 5 ms 3940 KB Output is correct
11 Correct 7 ms 3940 KB Output is correct
12 Correct 12 ms 4420 KB Output is correct
13 Correct 10 ms 4536 KB Output is correct
14 Correct 5 ms 4536 KB Output is correct
15 Correct 6 ms 4536 KB Output is correct
16 Correct 1345 ms 69696 KB Output is correct
17 Correct 114 ms 69696 KB Output is correct
18 Correct 192 ms 69696 KB Output is correct
19 Correct 1904 ms 95400 KB Output is correct
20 Correct 855 ms 102652 KB Output is correct
21 Correct 88 ms 102652 KB Output is correct
22 Correct 656 ms 102652 KB Output is correct