Submission #767663

# Submission time Handle Problem Language Result Execution time Memory
767663 2023-06-27T02:59:02 Z qwerasdfzxcl Wild Boar (JOI18_wild_boar) C++17
0 / 100
1 ms 724 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];
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 k1=0;k1<4;k1++){
            for (int j=0;j<4;j++){
                ll mn = INF;
                for (int k2=0;k2<4;k2++) if (abs(E[k1])!=abs(N.S[k2])) mn = min(mn, N.W[k2][j]);
                for (int i=0;i<4;i++) ret.W[i][j] = min(ret.W[i][j], W[i][k1] + mn);
            }
            ret.S[k1] = S[k1];
            ret.E[k1] = N.E[k1];
        }
        
		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});

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

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

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:210:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |  scanf("%d %d %d %d", &n, &m, &q, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:215:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:242:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 |  for (int i=1;i<=l;i++) scanf("%d", X+i);
      |                         ~~~~~^~~~~~~~~~~
wild_boar.cpp:247:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 |   scanf("%d %d", &pp, &qq);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -