oj.uz

Submission #767178

# Submission time Handle Problem Language Result Execution time Memory
767178 2023-06-26T13:26:07 Z qwerasdfzxcl Wild Boar (JOI18_wild_boar) C++17
47 / 100
 18000 ms 139808 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;

vector<pair<int, int>> adj0[6060];
pair<int, int> Edge[2020];
ll dist0[4040][4040], res0[4040];
int visited0[6060], F[2020];

vector<int> S[100100], E[100100], in[2020], out[2020];
vector<ll> W[100100];
int X[100100];
ll dp[100100][4];

void dijkstra(int m, int s, ll (*dist)[4040], ll *res, vector<pair<int, int>> *adj){
	int *visited = visited0 + 2020;
	fill(res-2020, res+2020, INF);
	fill(visited-2020, visited+4040, -1);

	priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
	vector<array<ll, 3>> st;
	
	res[s] = F[abs(s)];
	pq.push({F[abs(s)], s, 0});

	// printf("dijkstra from %d:\n", s);
	while(!pq.empty() || !st.empty()){
		array<ll, 3> tmp;
		if (!st.empty()) {tmp = st.back(); st.pop_back();}
		else {tmp = pq.top(); pq.pop();}

		auto [dist, cur, p] = tmp;
		
		if (visited[cur]==-2) continue;
		if (visited[cur]==-1){
			if (cur <= m){
				// printf(" dist[%lld] = %lld\n", cur, res[cur]);
				visited[cur] = -2;
				for (auto &[v, w]:adj[cur]) if (visited[v]!=-2){
					st.push_back({dist, v, cur});
				}
			}

			else{
				visited[cur] = abs(p);
				for (auto &[v, w]:adj[cur]) if (visited[v]!=-2 && abs(v)!=abs(p)){
					res[v] = dist + w;
					pq.push({res[v], v, cur});
				}
			}
		}

		else{
			for (auto &[v, w]:adj[cur]) if (abs(v)==visited[cur] && visited[v]!=-2){
				res[v] = dist + w;
				pq.push({res[v], v, cur});
			}

			visited[cur] = -2;
		}
	}


}

void initW(int p, ll (*dist)[4040]){
	W[p].push_back(INF);
	S[p].push_back(-1);
	E[p].push_back(-1);

	for (auto &s1:out[X[p]]){
		for (auto &e1:in[X[p+1]]){
			if (W[p].back() > dist[s1][e1]){
				W[p].back() = dist[s1][e1];
				S[p].back() = s1;
				E[p].back() = e1;
			}
		}
	}

	W[p].push_back(INF);
	S[p].push_back(-1);
	E[p].push_back(-1);

	for (auto &s2:out[X[p]]) if (s2!=S[p][0]){
		for (auto &e2:in[X[p+1]]) if (e2!=E[p][0]){
			if (W[p].back() > dist[s2][e2]){
				W[p].back() = dist[s2][e2];
				S[p].back() = s2;
				E[p].back() = e2;
			}
		}
	}

	W[p].push_back(INF);
	S[p].push_back(-1);
	E[p].push_back(-1);

	for (auto &s3:out[X[p]]) if (s3!=S[p][0]){
		for (auto &e3:in[X[p+1]]) if (e3!=E[p][1]){
			if (W[p].back() > dist[s3][e3]){
				W[p].back() = dist[s3][e3];
				S[p].back() = s3;
				E[p].back() = e3;
			}
		}
	}

	W[p].push_back(INF);
	S[p].push_back(-1);
	E[p].push_back(-1);

	for (auto &s4:out[X[p]]) if (s4!=S[p][1]){
		for (auto &e4:in[X[p+1]]) if (e4!=E[p][0]){
			if (W[p].back() > dist[s4][e4]){
				W[p].back() = dist[s4][e4];
				S[p].back() = s4;
				E[p].back() = e4;
			}
		}
	}

	// printf("init %d to %d -> ", X[p], X[p+1]);
	// for (int i=0;i<4;i++){
	// 	printf("(%lld / %d, %d) ", W[p][i], S[p][i], E[p][i]);
	// }
	// printf("\n");
}

int main(){
	int n, m, q, l;
	scanf("%d %d %d %d", &n, &m, &q, &l);

	vector<pair<int, int>> *adj = adj0 + m;
	for (int i=1;i<=m;i++){
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		Edge[i] = {x, y}; F[i] = z;

		adj[i].emplace_back(y+m, 0);
		adj[-i].emplace_back(x+m, 0);

		adj[x+m].emplace_back(i, z);
		adj[y+m].emplace_back(-i, z);

		out[x].push_back(i);
		out[y].push_back(-i);

		in[x].push_back(-i);
		in[y].push_back(i);
	}

	ll (*dist)[4040] = (ll (*)[4040])(&(dist0[2020][2020]));
	ll *res = res0 + 2020;

	// printf(" What %d %d\n", &(dist[1][-1]), &(dist0[2021][2019]));

	for (int i=1;i<=m;i++){
		dijkstra(m, i, dist, res, adj);
		// if (i==1) printf(" WTF %lld\n", res[-2]);
		for (int j=-m;j<=m;j++) dist[i][j] = res[j];
		
		dijkstra(m, -i, dist, res, adj);
		for (int j=-m;j<=m;j++) dist[-i][j] = res[j];
	}
	// printf("WTFF %lld (%d / %d)\n", dist[1][-2], &(dist[1][-2]), &(dist0[2021][2018]));

	for (int i=1;i<=l;i++) scanf("%d", X+i);
	int pp, qq;
	scanf("%d %d", &pp, &qq);
	X[pp] = qq;

	for (int i=1;i<l;i++){
		initW(i, dist);

		for (int j=0;j<4;j++){
			dp[i+1][j] = INF;
			if (i==1) {dp[i+1][j] = W[1][j]; continue;}
			if (W[i][j]==INF) continue;

			for (int k=0;k<4;k++) if (abs(E[i-1][k])!=abs(S[i][j])){
				dp[i+1][j] = min(dp[i+1][j], dp[i][k] + W[i][j]);
			}
		}
	}

	ll rans = *min_element(dp[l], dp[l]+4);
	if (rans==INF) rans = -1;
	printf("%lld\n", rans);
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |  scanf("%d %d %d %d", &n, &m, &q, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:170:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |  for (int i=1;i<=l;i++) scanf("%d", X+i);
      |                         ~~~~~^~~~~~~~~~~
wild_boar.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |  scanf("%d %d", &pp, &qq);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7636 KB Output is correct
2 Correct 4 ms 7764 KB Output is correct
3 Correct 4 ms 7764 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 4 ms 7668 KB Output is correct
6 Correct 3 ms 7764 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 4 ms 7764 KB Output is correct
9 Correct 3 ms 7764 KB Output is correct
10 Correct 4 ms 7764 KB Output is correct
11 Correct 4 ms 7636 KB Output is correct
12 Correct 4 ms 7764 KB Output is correct
13 Correct 4 ms 7728 KB Output is correct
14 Correct 4 ms 7764 KB Output is correct
15 Correct 3 ms 7636 KB Output is correct
16 Correct 4 ms 7764 KB Output is correct
17 Correct 5 ms 7636 KB Output is correct
18 Correct 4 ms 7636 KB Output is correct
19 Correct 4 ms 7764 KB Output is correct
20 Correct 4 ms 7764 KB Output is correct
21 Correct 4 ms 7764 KB Output is correct
22 Correct 4 ms 7764 KB Output is correct
23 Correct 4 ms 7764 KB Output is correct
24 Correct 4 ms 7636 KB Output is correct
25 Correct 4 ms 7636 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7636 KB Output is correct
2 Correct 4 ms 7764 KB Output is correct
3 Correct 4 ms 7764 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 4 ms 7668 KB Output is correct
6 Correct 3 ms 7764 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 4 ms 7764 KB Output is correct
9 Correct 3 ms 7764 KB Output is correct
10 Correct 4 ms 7764 KB Output is correct
11 Correct 4 ms 7636 KB Output is correct
12 Correct 4 ms 7764 KB Output is correct
13 Correct 4 ms 7728 KB Output is correct
14 Correct 4 ms 7764 KB Output is correct
15 Correct 3 ms 7636 KB Output is correct
16 Correct 4 ms 7764 KB Output is correct
17 Correct 5 ms 7636 KB Output is correct
18 Correct 4 ms 7636 KB Output is correct
19 Correct 4 ms 7764 KB Output is correct
20 Correct 4 ms 7764 KB Output is correct
21 Correct 4 ms 7764 KB Output is correct
22 Correct 4 ms 7764 KB Output is correct
23 Correct 4 ms 7764 KB Output is correct
24 Correct 4 ms 7636 KB Output is correct
25 Correct 4 ms 7636 KB Output is correct
26 Correct 4 ms 8020 KB Output is correct
27 Correct 54 ms 23168 KB Output is correct
28 Correct 53 ms 23156 KB Output is correct
29 Correct 162 ms 27372 KB Output is correct
30 Correct 393 ms 27428 KB Output is correct
31 Correct 2223 ms 27336 KB Output is correct
32 Correct 2152 ms 27420 KB Output is correct
33 Correct 151 ms 27384 KB Output is correct
34 Correct 130 ms 27336 KB Output is correct
35 Correct 2685 ms 27460 KB Output is correct
36 Correct 1367 ms 27360 KB Output is correct
37 Correct 129 ms 27340 KB Output is correct
38 Correct 135 ms 27384 KB Output is correct
39 Correct 592 ms 27360 KB Output is correct
40 Correct 122 ms 27348 KB Output is correct
41 Correct 116 ms 27344 KB Output is correct
42 Correct 682 ms 27348 KB Output is correct
43 Correct 112 ms 27372 KB Output is correct
44 Correct 99 ms 27348 KB Output is correct
45 Correct 66 ms 27364 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7636 KB Output is correct
2 Correct 4 ms 7764 KB Output is correct
3 Correct 4 ms 7764 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 4 ms 7668 KB Output is correct
6 Correct 3 ms 7764 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 4 ms 7764 KB Output is correct
9 Correct 3 ms 7764 KB Output is correct
10 Correct 4 ms 7764 KB Output is correct
11 Correct 4 ms 7636 KB Output is correct
12 Correct 4 ms 7764 KB Output is correct
13 Correct 4 ms 7728 KB Output is correct
14 Correct 4 ms 7764 KB Output is correct
15 Correct 3 ms 7636 KB Output is correct
16 Correct 4 ms 7764 KB Output is correct
17 Correct 5 ms 7636 KB Output is correct
18 Correct 4 ms 7636 KB Output is correct
19 Correct 4 ms 7764 KB Output is correct
20 Correct 4 ms 7764 KB Output is correct
21 Correct 4 ms 7764 KB Output is correct
22 Correct 4 ms 7764 KB Output is correct
23 Correct 4 ms 7764 KB Output is correct
24 Correct 4 ms 7636 KB Output is correct
25 Correct 4 ms 7636 KB Output is correct
26 Correct 4 ms 8020 KB Output is correct
27 Correct 54 ms 23168 KB Output is correct
28 Correct 53 ms 23156 KB Output is correct
29 Correct 162 ms 27372 KB Output is correct
30 Correct 393 ms 27428 KB Output is correct
31 Correct 2223 ms 27336 KB Output is correct
32 Correct 2152 ms 27420 KB Output is correct
33 Correct 151 ms 27384 KB Output is correct
34 Correct 130 ms 27336 KB Output is correct
35 Correct 2685 ms 27460 KB Output is correct
36 Correct 1367 ms 27360 KB Output is correct
37 Correct 129 ms 27340 KB Output is correct
38 Correct 135 ms 27384 KB Output is correct
39 Correct 592 ms 27360 KB Output is correct
40 Correct 122 ms 27348 KB Output is correct
41 Correct 116 ms 27344 KB Output is correct
42 Correct 682 ms 27348 KB Output is correct
43 Correct 112 ms 27372 KB Output is correct
44 Correct 99 ms 27348 KB Output is correct
45 Correct 66 ms 27364 KB Output is correct
46 Correct 137 ms 19536 KB Output is correct
47 Execution timed out 18073 ms 139808 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7636 KB Output is correct
2 Correct 4 ms 7764 KB Output is correct
3 Correct 4 ms 7764 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 4 ms 7668 KB Output is correct
6 Correct 3 ms 7764 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 4 ms 7764 KB Output is correct
9 Correct 3 ms 7764 KB Output is correct
10 Correct 4 ms 7764 KB Output is correct
11 Correct 4 ms 7636 KB Output is correct
12 Correct 4 ms 7764 KB Output is correct
13 Correct 4 ms 7728 KB Output is correct
14 Correct 4 ms 7764 KB Output is correct
15 Correct 3 ms 7636 KB Output is correct
16 Correct 4 ms 7764 KB Output is correct
17 Correct 5 ms 7636 KB Output is correct
18 Correct 4 ms 7636 KB Output is correct
19 Correct 4 ms 7764 KB Output is correct
20 Correct 4 ms 7764 KB Output is correct
21 Correct 4 ms 7764 KB Output is correct
22 Correct 4 ms 7764 KB Output is correct
23 Correct 4 ms 7764 KB Output is correct
24 Correct 4 ms 7636 KB Output is correct
25 Correct 4 ms 7636 KB Output is correct
26 Correct 4 ms 8020 KB Output is correct
27 Correct 54 ms 23168 KB Output is correct
28 Correct 53 ms 23156 KB Output is correct
29 Correct 162 ms 27372 KB Output is correct
30 Correct 393 ms 27428 KB Output is correct
31 Correct 2223 ms 27336 KB Output is correct
32 Correct 2152 ms 27420 KB Output is correct
33 Correct 151 ms 27384 KB Output is correct
34 Correct 130 ms 27336 KB Output is correct
35 Correct 2685 ms 27460 KB Output is correct
36 Correct 1367 ms 27360 KB Output is correct
37 Correct 129 ms 27340 KB Output is correct
38 Correct 135 ms 27384 KB Output is correct
39 Correct 592 ms 27360 KB Output is correct
40 Correct 122 ms 27348 KB Output is correct
41 Correct 116 ms 27344 KB Output is correct
42 Correct 682 ms 27348 KB Output is correct
43 Correct 112 ms 27372 KB Output is correct
44 Correct 99 ms 27348 KB Output is correct
45 Correct 66 ms 27364 KB Output is correct
46 Correct 137 ms 19536 KB Output is correct
47 Execution timed out 18073 ms 139808 KB Time limit exceeded
48 Halted 0 ms 0 KB -