답안 #235993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235993	2020-05-30T15:48:46 Z	cfalas	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	695 ms	113084 KB

crocodile

#include<bits/stdc++.h>
using namespace std;
#include "crocodile.h"
#define F first
#define S second
typedef pair<int, int> ii;
typedef vector<ii> vii;

vector<vii> adj;
#define INF 1500000000
map<int, bool> child[1000000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	adj.assign(n+1, vii());
	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]));
	}
	priority_queue<ii> q;
	for(int i=0;i<k;i++){
		q.push(ii(0, p[i]));
		q.push(ii(0, p[i]));
	}
	int cnt[n+1] = {};
	int ans=0;
	while(!q.empty()){
		ii t = q.top();
		q.pop();
		cnt[t.S]++;
		if(cnt[t.S]!=2) continue;
		if(t.S==0){ans=-t.F;break;}
		for(auto x : adj[t.S]){
			q.push(ii(-x.S+t.F, x.F));
		}
	}
	return ans;
}

Subtask #1

46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	47352 KB	Output is correct
2	Correct	30 ms	47352 KB	Output is correct
3	Correct	34 ms	47360 KB	Output is correct
4	Correct	31 ms	47224 KB	Output is correct
5	Correct	31 ms	47488 KB	Output is correct
6	Correct	31 ms	47352 KB	Output is correct
7	Correct	31 ms	47480 KB	Output is correct
8	Correct	30 ms	47420 KB	Output is correct

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	47352 KB	Output is correct
2	Correct	30 ms	47352 KB	Output is correct
3	Correct	34 ms	47360 KB	Output is correct
4	Correct	31 ms	47224 KB	Output is correct
5	Correct	31 ms	47488 KB	Output is correct
6	Correct	31 ms	47352 KB	Output is correct
7	Correct	31 ms	47480 KB	Output is correct
8	Correct	30 ms	47420 KB	Output is correct
9	Correct	34 ms	47736 KB	Output is correct
10	Correct	30 ms	47360 KB	Output is correct
11	Correct	32 ms	47488 KB	Output is correct
12	Correct	36 ms	48128 KB	Output is correct
13	Correct	34 ms	48256 KB	Output is correct
14	Correct	30 ms	47232 KB	Output is correct
15	Correct	31 ms	47360 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	47352 KB	Output is correct
2	Correct	30 ms	47352 KB	Output is correct
3	Correct	34 ms	47360 KB	Output is correct
4	Correct	31 ms	47224 KB	Output is correct
5	Correct	31 ms	47488 KB	Output is correct
6	Correct	31 ms	47352 KB	Output is correct
7	Correct	31 ms	47480 KB	Output is correct
8	Correct	30 ms	47420 KB	Output is correct
9	Correct	34 ms	47736 KB	Output is correct
10	Correct	30 ms	47360 KB	Output is correct
11	Correct	32 ms	47488 KB	Output is correct
12	Correct	36 ms	48128 KB	Output is correct
13	Correct	34 ms	48256 KB	Output is correct
14	Correct	30 ms	47232 KB	Output is correct
15	Correct	31 ms	47360 KB	Output is correct
16	Correct	645 ms	113084 KB	Output is correct
17	Correct	136 ms	60280 KB	Output is correct
18	Correct	142 ms	61816 KB	Output is correct
19	Correct	695 ms	108808 KB	Output is correct
20	Correct	425 ms	109228 KB	Output is correct
21	Correct	82 ms	52860 KB	Output is correct
22	Correct	658 ms	88604 KB	Output is correct