답안 #148125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148125	2019-08-31T14:06:06 Z	WhipppedCream	악어의 지하 도시 (IOI11_crocodile)	C++17	89 / 100	748 ms	63116 KB

crocodile

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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