oj.uz

Submission #131951

# Submission time Handle Problem Language Result Execution time Memory
131951 2019-07-18T05:53:51 Z 임유진(#3191) Wild Boar (JOI18_wild_boar) C++14
12 / 100
 3 ms 632 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -