Submission #767203

#	Time	Username	Problem	Language	Result	Execution time	Memory
767203		qwerasdfzxcl	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	4494 ms	231068 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];
ll (*dist)[4040];

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

struct Node{
	ll W[4][4];
	int S[4], E[4];

	Node(){}

	ll ans(){
		ll ret = INF;
		for (int i=0;i<4;i++){
			for (int j=0;j<4;j++){
				ret = min(ret, W[i][j]);
			}
		}

		return ret==INF?-1:ret;
	}

	Node operator + (const Node &N) const{
		Node ret;
		for (int i=0;i<4;i++){
			ret.S[i] = S[i];
			ret.E[i] = N.E[i];
			for (int j=0;j<4;j++){
				ret.W[i][j] = INF;
				for (int k1=0;k1<4;k1++){
					for (int k2=0;k2<4;k2++) if (abs(E[k1])!=abs(N.S[k2])){
						ret.W[i][j] = min(ret.W[i][j], W[i][k1] + N.W[k2][j]);
					}
				}
			}
		}

		return ret;
	}
};

Node initW(int p);

struct Seg{
	Node tree[400400];
	void init(int i, int l, int r){
		if (l==r){
			tree[i] = initW(l);
			return;
		} 
		
		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);
		tree[i] = tree[i<<1] + tree[i<<1|1];
	}

	void update(int i, int l, int r, int p){
		if (r<p || p<l) return;
		if (l==r){
			tree[i] = initW(l);
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, p); update(i<<1|1, m+1, r, p);
		tree[i] = tree[i<<1] + tree[i<<1|1];
	}

}tree;

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;
		}
	}


}

map<int, Node> mp[2020];
Node initW(int p){
	vector<ll> W;
	vector<int> S, E;
	if (mp[X[p]].find(X[p+1])!=mp[X[p]].end()){
		return mp[X[p]][X[p+1]];
	}

	W.push_back(INF);
	S.push_back(-1);
	E.push_back(-1);

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

	W.push_back(INF);
	S.push_back(-1);
	E.push_back(-1);

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

	W.push_back(INF);
	S.push_back(-1);
	E.push_back(-1);

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

	W.push_back(INF);
	S.push_back(-1);
	E.push_back(-1);

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

	Node ret;
	for (int i=0;i<4;i++){
		for (int j=0;j<4;j++){
			if (i!=j) ret.W[i][j] = INF;
			else ret.W[i][j] = W[i];
		}

		ret.S[i] = S[i];
		ret.E[i] = E[i];
	}
	mp[X[p]][X[p+1]] = ret;
	return ret;

	// 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);
	}

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

	for (int i=1;i<=m;i++){
		dijkstra(m, i, dist, res, adj);
		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];
	}

	for (int i=1;i<=l;i++) scanf("%d", X+i);

	tree.init(1, 1, l-1);
	while(q--){
		int pp, qq;
		scanf("%d %d", &pp, &qq);
		X[pp] = qq;
		if (pp > 1) tree.update(1, 1, l-1, pp-1);
		if (pp < l) tree.update(1, 1, l-1, pp);

		printf("%lld\n", tree.tree[1].ans());
	}

	// 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:219:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |  scanf("%d %d %d %d", &n, &m, &q, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:224:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:251:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |  for (int i=1;i<=l;i++) scanf("%d", X+i);
      |                         ~~~~~^~~~~~~~~~~
wild_boar.cpp:256:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  256 |   scanf("%d %d", &pp, &qq);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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