Submission #767180

#	Time	Username	Problem	Language	Result	Execution time	Memory
767180		qwerasdfzxcl	Wild Boar (JOI18_wild_boar)	C++17	47 / 100	3112 ms	39784 KiB

wild_boar

#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];

		if (i>500) return 0;
	}
	// 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 (stderr)

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:172:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |  for (int i=1;i<=l;i++) scanf("%d", X+i);
      |                         ~~~~~^~~~~~~~~~~
wild_boar.cpp:174:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |  scanf("%d %d", &pp, &qq);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38