Submission #132226

#	Time	Username	Problem	Language	Result	Execution time	Memory
132226		youngyojun	Wild Boar (JOI18_wild_boar)	C++11	100 / 100	15858 ms	826664 KiB

wild_boar

#include <bits/stdc++.h>
#define eb emplace_back
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;

const int MAXK = 100005;

ll dp[MAXK*3][7][7];

vector<int> G[2005];

ll F[2005][2005][7];
int FVA[2005][2005][7], FVB[2005][2005][7];
int FA[2005][2005][5], FB[2005][2005][5];

ll E[4005][4005];

int A[2005], B[2005], C[2005];
int D[MAXK];

int N, M, K, Q;

ll get() { return *min_element(dp[1][0], dp[1][6]+7); }

void cal(int i, int s, int e) {
	if(s == e) {
		for(int a = 0; a < 7; a++) for(int b = 0; b < 7; b++)
			dp[i][a][b] = a == b ? F[D[s]][D[s+1]][a] : INFLL;
		return;
	}
	int m = (s+e) >> 1;
	for(int a = 0; a < 7; a++) for(int b = 0; b < 7; b++) {
		ll &ret = dp[i][a][b]; ret = INFLL;
		for(int c = 0; c < 7; c++) for(int d = 0; d < 7; d++) {
			if(FVB[D[m]][D[m+1]][c] == FVA[D[m+1]][D[m+2]][d]) continue;
			ll t = dp[i<<1][a][c] + dp[i<<1|1][d][b];
			if(t < ret) ret = t;
		}
	}
}

void initSeg(int i, int s, int e) {
	if(s != e) {
		int m = (s+e) >> 1;
		initSeg(i<<1, s, m);
		initSeg(i<<1|1, m+1, e);
	}
	cal(i, s, e);
}

void upd(int i, int s, int e, int x1, int x2) {
	if(s == e) {
		cal(i, s, e);
		return;
	}
	int m = (s+e) >> 1;
	if(x1 <= m) upd(i<<1, s, m, x1, m < x2 ? x1 : x2);
	if(m < x2) upd(i<<1|1, m+1, e, x1 <= m ? x2 : x1, x2);
	cal(i, s, e);
}

int getSidx(int e) { return ((e&1) ? B : A)[e>>1]; }
int getEidx(int e) { return ((e&1) ? A : B)[e>>1]; }

int bfE[2005];
bitset<2005> chk;
void doDijk(ll E[], int se) {
	chk.reset();
	priority_queue<pli, vector<pli>, greater<pli>> PQ;
	fill(E, E+(M<<1), INFLL);
	E[se] = 0;
	PQ.emplace(0, se);
	for(ll dst; !PQ.empty();) {
		int eidx; tie(dst, eidx) = PQ.top(); PQ.pop();
		if(E[eidx] < dst) continue;
		int v = getEidx(eidx);
		if(chk[v]) {
			int e = bfE[v]^1;
			if(e != (eidx^1)) {
				ll ndst = dst + C[e>>1];
				if(ndst < E[e]) {
					E[e] = ndst;
					PQ.emplace(ndst, e);
				}
			}
		} else {
			chk[v] = true;
			bfE[v] = eidx;
			for(int e : G[v]) if(e != (eidx^1)) {
				ll ndst = dst + C[e>>1];
				if(E[e] <= ndst) continue;
				E[e] = ndst;
				PQ.emplace(ndst, e);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M >> Q >> K;
	for(int i = 0; i < M; i++) {
		cin >> A[i] >> B[i] >> C[i];
		if(A[i] > B[i]) swap(A[i], B[i]);
		G[A[i]].eb(i<<1);
		G[B[i]].eb(i<<1|1);
	}
	for(int i = 1; i <= K; i++) cin >> D[i];

	for(int i = M<<1; i--;) doDijk(E[i], i);

	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) if(j != i) {
		fill(F[i][j], F[i][j]+7, INFLL);
		fill(FA[i][j], FA[i][j]+5, -1);
		fill(FB[i][j], FB[i][j]+5, -1);

		// Case 0
		for(int e : G[i]) if(getEidx(e) == j) F[i][j][0] = C[e>>1];

		// Case 1
		int &a0 = FA[i][j][0], &b0 = FB[i][j][0], ea0 = -1, eb0 = -1;
		ll &c1 = F[i][j][1];
		for(int ea : G[i]) for(int eb : G[j]) {
			ll c = E[ea][eb^1] + C[ea>>1];
			if(c1 <= c) continue;
			a0 = getEidx(ea); b0 = getEidx(eb); c1 = c;
			ea0 = ea; eb0 = eb;
		}
		if(ea0 < 0) continue;
		eb0 ^= 1;

		// Case 2
		int &a1 = FA[i][j][1];
		ll &c2 = F[i][j][2];
		for(int ea : G[i]) if(ea != ea0) {
			ll c = E[ea][eb0] + C[ea>>1];
			if(c2 <= c) continue;
			a1 = getEidx(ea); c2 = c;
		}

		// Case 3
		int &b1 = FB[i][j][1];
		ll &c3 = F[i][j][3];
		for(int eb : G[j]) if(eb != (eb0^1)) {
			ll c = E[ea0][eb^1] + C[ea0>>1];
			if(c3 <= c) continue;
			b1 = getEidx(eb); c3 = c;
		}

		// Case 4
		int &a2 = FA[i][j][2], &b2 = FB[i][j][2];
		ll &c4 = F[i][j][4];
		for(int ea : G[i]) for(int eb : G[j]) if(ea != ea0 && eb != (eb0^1)) {
			ll c = E[ea][eb^1] + C[ea>>1];
			if(c4 <= c) continue;
			a2 = getEidx(ea); b2 = getEidx(eb); c4 = c;
		}
		if(a2 < 0) continue;

		// Case 5
		int &a3 = FA[i][j][3], &b3 = FB[i][j][3];
		ll &c5 = F[i][j][5];
		for(int ea : G[i]) for(int eb : G[j]) {
			int av = getEidx(ea), bv = getEidx(eb);
			if(av == a0 || bv == b2) continue;
			ll c = E[ea][eb^1] + C[ea>>1];
			if(c5 <= c) continue;
			a3 = av; b3 = bv; c5 = c;
		}

		// Case 6
		int &a4 = FA[i][j][4], &b4 = FB[i][j][4];
		ll &c6 = F[i][j][6];
		for(int ea : G[i]) for(int eb : G[j]) {
			int av = getEidx(ea), bv = getEidx(eb);
			if(av == a2 || bv == b0) continue;
			ll c = E[ea][eb^1] + C[ea>>1];
			if(c6 <= c) continue;
			a4 = av; b4 = bv; c6 = c;
		}
	}

	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) {
		int *fa = FA[i][j], *fb = FB[i][j];
		int *fva = FVA[i][j], *fvb = FVB[i][j];
		fva[0] = j; fvb[0] = i;
		fva[1] = fa[0]; fvb[1] = fb[0];
		fva[2] = fa[1]; fvb[2] = fb[0];
		fva[3] = fa[0]; fvb[3] = fb[1];
		fva[4] = fa[2]; fvb[4] = fb[2];
		fva[5] = fa[3]; fvb[5] = fb[3];
		fva[6] = fa[4]; fvb[6] = fb[4];
	}

	initSeg(1, 1, K-1);
	for(int a, b; Q--;) {
		cin >> a >> b;
		D[a] = b;
		upd(1, 1, K-1, a-1, a);
		ll t = get();
		if(INFLL <= t) puts("-1");
		else printf("%lld\n", t);
	}
	return 0;
}

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