답안 #140353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140353	2019-08-02T15:41:57 Z	muradeyn	악어의 지하 도시 (IOI11_crocodile)	C++14	89 / 100	2000 ms	51804 KB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxx = 100000;

int x , y;
int ext[maxx];
long long ans[maxx];

vector< pair<int,int> >v[maxx];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	for (int i = 0;i<n;i++)ans[i] = INT_MAX;
	for (int i = 0;i<k;i++)ext[p[i]] = 1 , ans[p[i]] = 0;
	for (int i = 0;i<m;i++) {
		x = r[i][0]; y = r[i][1];
		if (!ext[x])v[y].push_back({x , l[i]});
		if (!ext[y])v[x].push_back({y , l[i]});
	}
	bool f = true;
	while (f) {
		f = false;
		vector<int>thru[maxx];
		for (int i = 0;i<n;i++) {
			if (ans[i] == INT_MAX)continue;
			for (auto to : v[i]) thru[to.F].push_back(to.S + ans[i]);
		}
		for (int i = 0;i<n;i++) {
			if (thru[i].size() < 2)continue;
			sort(thru[i].begin(),thru[i].end());
			if (thru[i][1] < ans[i]) {
				f = true;
				ans[i] = thru[i][1];
			}
		}
	}
	return ans[0];
}

Subtask #1

46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	7 ms	4984 KB	Output is correct
3	Correct	8 ms	5112 KB	Output is correct
4	Correct	10 ms	5112 KB	Output is correct
5	Correct	9 ms	5112 KB	Output is correct
6	Correct	8 ms	5112 KB	Output is correct
7	Correct	9 ms	5112 KB	Output is correct
8	Correct	184 ms	5172 KB	Output is correct

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	7 ms	4984 KB	Output is correct
3	Correct	8 ms	5112 KB	Output is correct
4	Correct	10 ms	5112 KB	Output is correct
5	Correct	9 ms	5112 KB	Output is correct
6	Correct	8 ms	5112 KB	Output is correct
7	Correct	9 ms	5112 KB	Output is correct
8	Correct	184 ms	5172 KB	Output is correct
9	Correct	12 ms	5368 KB	Output is correct
10	Correct	36 ms	5116 KB	Output is correct
11	Correct	11 ms	5112 KB	Output is correct
12	Correct	22 ms	5624 KB	Output is correct
13	Correct	11 ms	5752 KB	Output is correct
14	Correct	10 ms	5112 KB	Output is correct
15	Correct	15 ms	5240 KB	Output is correct

Subtask #3

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	7 ms	4984 KB	Output is correct
3	Correct	8 ms	5112 KB	Output is correct
4	Correct	10 ms	5112 KB	Output is correct
5	Correct	9 ms	5112 KB	Output is correct
6	Correct	8 ms	5112 KB	Output is correct
7	Correct	9 ms	5112 KB	Output is correct
8	Correct	184 ms	5172 KB	Output is correct
9	Correct	12 ms	5368 KB	Output is correct
10	Correct	36 ms	5116 KB	Output is correct
11	Correct	11 ms	5112 KB	Output is correct
12	Correct	22 ms	5624 KB	Output is correct
13	Correct	11 ms	5752 KB	Output is correct
14	Correct	10 ms	5112 KB	Output is correct
15	Correct	15 ms	5240 KB	Output is correct
16	Execution timed out	2041 ms	51804 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-