Submission #64626

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
64626	2018-08-05T06:11:13 Z	gnoor	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1484 ms	83944 KB

crocodile

#include "crocodile.h"

#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

struct ei {
	int vec,wgt;
};

bool operator< (const ei &a, const ei &b) {
	return a.wgt>b.wgt;
}

int dis[100100];
int cnt[100100];
vector<ei> pth[100100];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(dis,63,sizeof(dis));
	for (int i=0;i<M;i++) {
		pth[R[i][0]].push_back(ei{R[i][1],L[i]});
		pth[R[i][1]].push_back(ei{R[i][0],L[i]});
	}
	priority_queue<ei> q;
	for (int i=0;i<K;i++) {
		cnt[P[i]]=1;
		q.push(ei{P[i],0});	
	}
	int now,nowdis;
	while (!q.empty()) {
		now=q.top().vec;
		nowdis=q.top().wgt;
		q.pop();
		cnt[now]++;
		if (cnt[now]!=2) continue;
		dis[now]=nowdis;
		for (auto &i:pth[now]) {
			q.push(ei{i.vec,dis[now]+i.wgt});
		}
	}
	return dis[0];
}

Subtask #1

46.0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	5 ms	3180 KB	Output is correct
3	Correct	6 ms	3236 KB	Output is correct
4	Correct	8 ms	3332 KB	Output is correct
5	Correct	7 ms	3408 KB	Output is correct
6	Correct	6 ms	3424 KB	Output is correct
7	Correct	5 ms	3504 KB	Output is correct
8	Correct	6 ms	3504 KB	Output is correct

Subtask #2

43.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	5 ms	3180 KB	Output is correct
3	Correct	6 ms	3236 KB	Output is correct
4	Correct	8 ms	3332 KB	Output is correct
5	Correct	7 ms	3408 KB	Output is correct
6	Correct	6 ms	3424 KB	Output is correct
7	Correct	5 ms	3504 KB	Output is correct
8	Correct	6 ms	3504 KB	Output is correct
9	Correct	10 ms	3940 KB	Output is correct
10	Correct	6 ms	3940 KB	Output is correct
11	Correct	7 ms	3940 KB	Output is correct
12	Correct	14 ms	4472 KB	Output is correct
13	Correct	12 ms	4688 KB	Output is correct
14	Correct	7 ms	4688 KB	Output is correct
15	Correct	7 ms	4688 KB	Output is correct

Subtask #3

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	5 ms	3180 KB	Output is correct
3	Correct	6 ms	3236 KB	Output is correct
4	Correct	8 ms	3332 KB	Output is correct
5	Correct	7 ms	3408 KB	Output is correct
6	Correct	6 ms	3424 KB	Output is correct
7	Correct	5 ms	3504 KB	Output is correct
8	Correct	6 ms	3504 KB	Output is correct
9	Correct	10 ms	3940 KB	Output is correct
10	Correct	6 ms	3940 KB	Output is correct
11	Correct	7 ms	3940 KB	Output is correct
12	Correct	14 ms	4472 KB	Output is correct
13	Correct	12 ms	4688 KB	Output is correct
14	Correct	7 ms	4688 KB	Output is correct
15	Correct	7 ms	4688 KB	Output is correct
16	Correct	1327 ms	73572 KB	Output is correct
17	Correct	119 ms	73572 KB	Output is correct
18	Correct	158 ms	73572 KB	Output is correct
19	Correct	1484 ms	83944 KB	Output is correct
20	Correct	770 ms	83944 KB	Output is correct
21	Correct	74 ms	83944 KB	Output is correct
22	Correct	823 ms	83944 KB	Output is correct