Submission #77844

#	Time	Username	Problem	Language	Result	Execution time	Memory
77844		tmwilliamlin168	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	369 ms	27132 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define a array

const int mxN=2e3, mxL=1e5;
const ll INF=1e18;
int n, m, t, l, x[mxL], ai, bi, ci;
vector<a<int, 2>> adj[mxN];
a<ll, 3> d[mxN][mxN][4], st[1<<18][4];
priority_queue<a<ll, 4>, vector<a<ll, 4>>, greater<a<ll, 4>>> pq;

void dij(int s, a<ll, 3> d[mxN][4]) {
	for(int i=0; i<n; ++i)
		for(int j=0; j<4; ++j)
			d[i][j]={INF};
	for(a<int, 2> e : adj[s])
		pq.push({e[0], e[1], e[1], s});
	while(pq.size()) {
		a<ll, 4> u=pq.top();
		pq.pop();
		int i=0, c1=0, c2=0, c3=0;
		while(i<4&&d[u[1]][i][0]<INF) {
			c1+=d[u[1]][i][1]==u[2]&&d[u[1]][i][2]==u[3];
			c2+=d[u[1]][i][1]==u[2];
			c3+=d[u[1]][i][2]==u[3];
			++i;
		}
		if(i>=4||c1||c2>1||c3>1)
			continue;
		d[u[1]][i]={u[0], u[2], u[3]};
		for(a<int, 2> e : adj[u[1]])
			if(e[1]!=u[3])
				pq.push({u[0]+e[0], e[1], u[2], u[1]});
	}
}

void upd(int l1, int i=1, int l2=0, int r2=l-2) {
	if(l2==r2) {
		for(int j=0; j<4; ++j)
			st[i][j]=d[x[l1]][x[l1+1]][j];
		return;
	}
	int m2=(l2+r2)/2;
	if(l1<=m2)
		upd(l1, 2*i, l2, m2);
	else
		upd(l1, 2*i+1, m2+1, r2);
	st[i][0]={0, -1, -1};
	auto b=[&](const int &j) {
		st[i][j]={INF, -1, -1};
		for(int k=0; k<4; ++k)
			for(int l=0; l<4; ++l)
				if(st[2*i][k][1]!=st[i][j&1?0:3][1]&&st[2*i+1][l][2]!=st[i][j&2?0:3][2]&&st[2*i][k][2]!=st[2*i+1][l][1])
					st[i][j]=min(a<ll, 3>{st[2*i][k][0]+st[2*i+1][l][0], st[2*i][k][1], st[2*i+1][l][2]}, st[i][j]);
	};
	b(3);
	for(int j=0; j<3; ++j)
		b(j);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> t >> l;
	while(m--) {
		cin >> ai >> bi >> ci, --ai, --bi;
		adj[ai].push_back({ci, bi});
		adj[bi].push_back({ci, ai});
	}
	for(int i=0; i<n; ++i)
		dij(i, d[i]);
	for(int i=0; i<l; ++i) {
		cin >> x[i], --x[i];
		if(i)
			upd(i-1);
	}
	while(t--) {
		int pk, qk;
		cin >> pk >> qk, --pk, --qk;
		x[pk]=qk;
		if(pk)
			upd(pk-1);
		if(pk<l-1)
			upd(pk);
		ll ans=min({st[1][0][0], st[1][1][0], st[1][2][0], st[1][3][0]});
		cout << (ans>=INF?-1:ans) << "\n";
	}
}

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