oj.uz

Submission #388597

# Submission time Handle Problem Language Result Execution time Memory
388597 2021-04-12T08:28:29 Z mariowong Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 945 ms 100460 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

struct edge{
	int node;
	long long w;
}nw,now;

int ans;
vector <edge> e[100005];
priority_queue <pair<long long,int>  > q;
bool vis[100005][5];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for (int i=0;i<M;i++){
		now.w=L[i];
		now.node=R[i][0];	e[R[i][1]].push_back(now);
		now.node=R[i][1];	e[R[i][0]].push_back(now);
	}
	for (int i=0;i<K;i++){
		q.push(make_pair(0,P[i]));
		q.push(make_pair(0,P[i]));
	}
	while (!q.empty()){
		now.w=-q.top().first; now.node=q.top().second;
		if (!vis[now.node][0])
		vis[now.node][0]=true;
		else
		if (!vis[now.node][1]){
			vis[now.node][1]=true;
			if (now.node == 0) ans=now.w;
			for (int i=0;i<e[now.node].size();i++){
				if (!vis[e[now.node][i].node][1])
				q.push(make_pair(-(now.w+e[now.node][i].w),e[now.node][i].node));
			}
		}
		q.pop();
	}
	return ans;
}

Compilation message

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

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2804 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2780 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2804 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2780 KB Output is correct
9 Correct 4 ms 3276 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2800 KB Output is correct
12 Correct 7 ms 3664 KB Output is correct
13 Correct 7 ms 3796 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2804 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2780 KB Output is correct
9 Correct 4 ms 3276 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2800 KB Output is correct
12 Correct 7 ms 3664 KB Output is correct
13 Correct 7 ms 3796 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 820 ms 96996 KB Output is correct
17 Correct 84 ms 16580 KB Output is correct
18 Correct 120 ms 19000 KB Output is correct
19 Correct 945 ms 100460 KB Output is correct
20 Correct 498 ms 84200 KB Output is correct
21 Correct 46 ms 9412 KB Output is correct
22 Correct 512 ms 64120 KB Output is correct