답안 #131951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131951	2019-07-18T05:53:51 Z	임유진(#3191)	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	3 ms	632 KB

wild_boar

#include <bits/stdc++.h>

using namespace std;

#define MAXN 2005
#define fi first
#define se second

typedef long long lint;
typedef pair<lint, int> pli;

const lint LINF = 1ll << 60;
int A[MAXN], B[MAXN], C[MAXN], X[MAXN];
vector<int> ed[2 * MAXN];
vector<lint> dp;
vector<int> in[MAXN], out[MAXN];

int main() {
	int N, M, T, L;
	int P, Q;

	scanf("%d%d%d%d", &N, &M, &T, &L);
	for(int i = 0; i < M; i++) scanf("%d%d%d", A + i, B + i, C + i);
	for(int i = 0; i < L; i++) scanf("%d", X + i);
	scanf("%d%d", &P, &Q);

	X[P - 1] = Q;
	for(int i = 1; i <= N; i++) {
		for(int j = 0; j < M; j++) {
			if(A[j] == i) {
				out[i].push_back(j);
				in[i].push_back(j + M);
			}
			else if(B[j] == i) {
				in[i].push_back(j);
				out[i].push_back(j + M);
			}
		}
		for(auto a : in[i]) for(auto b : out[i]) if(a % M != b % M) ed[a].push_back(b);
	}

	dp.resize(2 * M, 0ll);
	for(auto a : out[X[0]]) dp[a] = C[a % M];
	for(int i = 0; i < L - 1; i++) {
		priority_queue<pli, vector<pli>, greater<pli> > pq;
		vector<lint> v(2 * M, LINF);
		for(auto a : out[X[i]]) {
			v[a] = dp[a];
			pq.push(make_pair(dp[a], a));
		}
		swap(dp, v);
		while(!pq.empty()) {
			pli t = pq.top();
			pq.pop();
			if(dp[t.se] != t.fi) continue;
			for(auto a : ed[t.se]) if(t.fi + C[a % M] < dp[a]) {
				dp[a] = t.fi + C[a % M];
				pq.push(make_pair(dp[a], a));
			}
		}
	}

	lint ans = LINF;
	for(auto a : in[X[L - 1]]) ans = min(ans, dp[a]);
	printf("%lld", ans == LINF ? -1 : ans);
	return 0;
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &M, &T, &L);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:23:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < M; i++) scanf("%d%d%d", A + i, B + i, C + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:24:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < L; i++) scanf("%d", X + i);
                             ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &P, &Q);
  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	508 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	504 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	504 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	504 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	508 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	504 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	504 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	504 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Execution timed out	3 ms	632 KB	Time limit exceeded (wall clock)
28	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	508 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	504 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	504 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	504 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Execution timed out	3 ms	632 KB	Time limit exceeded (wall clock)
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	508 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	504 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	504 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	504 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	504 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Execution timed out	3 ms	632 KB	Time limit exceeded (wall clock)
28	Halted	0 ms	0 KB	-

답안 #131951

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0