답안 #262146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262146	2020-08-12T12:02:50 Z	nandonathaniel	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	1295 ms	78412 KB

crocodile

#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long,int> pli;
const int MAXN=100005;
const long long INF=1e18;

vector<pii> adj[MAXN];
long long dist[MAXN];
priority_queue<pli,vector<pli>,greater<pli> > PQ;
bool keluar[MAXN];
int muncul[MAXN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for(int i=0;i<M;i++){
		adj[R[i][0]].push_back({R[i][1],L[i]});
		adj[R[i][1]].push_back({R[i][0],L[i]});
	}
	for(int i=0;i<N;i++)dist[i]=INF;
	for(int i=0;i<K;i++){
		dist[P[i]]=0;
		keluar[P[i]]=true;
		PQ.push({dist[P[i]],P[i]});
	}
	while(!PQ.empty()){
		pii now=PQ.top();
		PQ.pop();
		muncul[now.second]++;
		if(!keluar[now.second]){
			if(muncul[now.second]!=2)continue;
		}
		else{
			if(muncul[now.second]!=1)continue;
		}
		dist[now.second]=now.first;
		for(auto nxt : adj[now.second]){
			PQ.push({dist[now.second]+nxt.second,nxt.first});
		}
	}
	return dist[0];
}

Subtask #1

46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	2 ms	2688 KB	Output is correct
4	Correct	3 ms	2816 KB	Output is correct
5	Correct	3 ms	2816 KB	Output is correct
6	Correct	3 ms	2816 KB	Output is correct
7	Correct	3 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	2 ms	2688 KB	Output is correct
4	Correct	3 ms	2816 KB	Output is correct
5	Correct	3 ms	2816 KB	Output is correct
6	Correct	3 ms	2816 KB	Output is correct
7	Correct	3 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	5 ms	3328 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Correct	4 ms	2944 KB	Output is correct
12	Correct	11 ms	3840 KB	Output is correct
13	Correct	9 ms	3836 KB	Output is correct
14	Correct	2 ms	2688 KB	Output is correct
15	Correct	3 ms	2816 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	2 ms	2688 KB	Output is correct
4	Correct	3 ms	2816 KB	Output is correct
5	Correct	3 ms	2816 KB	Output is correct
6	Correct	3 ms	2816 KB	Output is correct
7	Correct	3 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	5 ms	3328 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Correct	4 ms	2944 KB	Output is correct
12	Correct	11 ms	3840 KB	Output is correct
13	Correct	9 ms	3836 KB	Output is correct
14	Correct	2 ms	2688 KB	Output is correct
15	Correct	3 ms	2816 KB	Output is correct
16	Correct	1182 ms	75100 KB	Output is correct
17	Correct	107 ms	11768 KB	Output is correct
18	Correct	161 ms	13128 KB	Output is correct
19	Correct	1295 ms	78412 KB	Output is correct
20	Correct	838 ms	72080 KB	Output is correct
21	Correct	56 ms	7288 KB	Output is correct
22	Correct	668 ms	35332 KB	Output is correct