oj.uz

Submission #148125

# Submission time Handle Problem Language Result Execution time Memory
148125 2019-08-31T14:06:06 Z WhipppedCream Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 748 ms 63116 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define ii pair<int, int>
#define st first
#define nd second
#define maxn 100005
vector< ii > adj[maxn];
bool mark[maxn];
ii dist[maxn];
struct node
{
	int u, d;
	node(){}
	node(int _u, int _d)
	{
		u = _u;
		d = _d;
	}
	bool operator < (node other) const
	{
		return d> other.d;
	}
};
int travel_plan(int n, int m, int R[][2], int *L, int k, int *P)
{
    priority_queue< node > pq;
    for(int i = 0; i< n; i++)
    {
        dist[i].st = dist[i].nd = 1e9;
        pq.push(node(i, 1e9));
    }
	for(int i = 0; i< m; i++)
	{
		adj[R[i][0]].push_back(ii(R[i][1], L[i]));
		adj[R[i][1]].push_back(ii(R[i][0], L[i]));
	}
	for(int i = 0; i< k; i++)
	{
		pq.push(node(P[i], 0));
		dist[P[i]].st = dist[P[i]].nd = 0;
	}
	while(!pq.empty())
	{
		node x = pq.top();
		pq.pop();
		int u = x.u;
        if(x.d != dist[u].nd) continue;
		for(int i = 0; i< (int) adj[u].size(); i++)
		{
			ii k = adj[u][i];
			int v = k.st, w = k.nd;
			int nw = w+dist[u].nd;
			if(nw < dist[v].st)
			{
				dist[v].nd = dist[v].st;
				dist[v].st = nw;
				pq.push(node(v, dist[v].nd));
			}
			else if(nw < dist[v].nd)
			{
				dist[v].nd = nw;
				pq.push(node(v, dist[v].nd));
			}
		}
	}
	return dist[0].nd;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2936 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 8 ms 3192 KB Output is correct
13 Correct 7 ms 3192 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2936 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 8 ms 3192 KB Output is correct
13 Correct 7 ms 3192 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 645 ms 58004 KB Output is correct
17 Correct 124 ms 15976 KB Output is correct
18 Correct 168 ms 17384 KB Output is correct
19 Correct 748 ms 63116 KB Output is correct
20 Correct 421 ms 49704 KB Output is correct
21 Correct 54 ms 8308 KB Output is correct
22 Incorrect 397 ms 46452 KB Output isn't correct