oj.uz

Submission #132226

# Submission time Handle Problem Language Result Execution time Memory
132226 2019-07-18T14:22:37 Z youngyojun Wild Boar (JOI18_wild_boar) C++11
100 / 100
 15858 ms 826664 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 2 ms 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 632 KB Output is correct
23 Correct 2 ms 632 KB Output is correct
24 Correct 2 ms 632 KB Output is correct
25 Correct 2 ms 632 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 2 ms 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 632 KB Output is correct
23 Correct 2 ms 632 KB Output is correct
24 Correct 2 ms 632 KB Output is correct
25 Correct 2 ms 632 KB Output is correct
26 Correct 5 ms 1400 KB Output is correct
27 Correct 939 ms 106452 KB Output is correct
28 Correct 925 ms 106432 KB Output is correct
29 Correct 905 ms 110472 KB Output is correct
30 Correct 782 ms 110584 KB Output is correct
31 Correct 872 ms 110600 KB Output is correct
32 Correct 863 ms 110468 KB Output is correct
33 Correct 955 ms 113572 KB Output is correct
34 Correct 948 ms 113500 KB Output is correct
35 Correct 929 ms 113332 KB Output is correct
36 Correct 737 ms 113228 KB Output is correct
37 Correct 939 ms 113440 KB Output is correct
38 Correct 980 ms 117188 KB Output is correct
39 Correct 784 ms 117112 KB Output is correct
40 Correct 968 ms 117096 KB Output is correct
41 Correct 963 ms 117048 KB Output is correct
42 Correct 794 ms 119492 KB Output is correct
43 Correct 976 ms 121488 KB Output is correct
44 Correct 974 ms 121464 KB Output is correct
45 Correct 805 ms 126584 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 2 ms 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 632 KB Output is correct
23 Correct 2 ms 632 KB Output is correct
24 Correct 2 ms 632 KB Output is correct
25 Correct 2 ms 632 KB Output is correct
26 Correct 5 ms 1400 KB Output is correct
27 Correct 939 ms 106452 KB Output is correct
28 Correct 925 ms 106432 KB Output is correct
29 Correct 905 ms 110472 KB Output is correct
30 Correct 782 ms 110584 KB Output is correct
31 Correct 872 ms 110600 KB Output is correct
32 Correct 863 ms 110468 KB Output is correct
33 Correct 955 ms 113572 KB Output is correct
34 Correct 948 ms 113500 KB Output is correct
35 Correct 929 ms 113332 KB Output is correct
36 Correct 737 ms 113228 KB Output is correct
37 Correct 939 ms 113440 KB Output is correct
38 Correct 980 ms 117188 KB Output is correct
39 Correct 784 ms 117112 KB Output is correct
40 Correct 968 ms 117096 KB Output is correct
41 Correct 963 ms 117048 KB Output is correct
42 Correct 794 ms 119492 KB Output is correct
43 Correct 976 ms 121488 KB Output is correct
44 Correct 974 ms 121464 KB Output is correct
45 Correct 805 ms 126584 KB Output is correct
46 Correct 199 ms 22484 KB Output is correct
47 Correct 3539 ms 274876 KB Output is correct
48 Correct 3484 ms 338732 KB Output is correct
49 Correct 3509 ms 396268 KB Output is correct
50 Correct 3492 ms 396400 KB Output is correct
51 Correct 3639 ms 396244 KB Output is correct
52 Correct 4142 ms 396616 KB Output is correct
53 Correct 4119 ms 396596 KB Output is correct
54 Correct 4148 ms 396356 KB Output is correct
55 Correct 4158 ms 396312 KB Output is correct
56 Correct 4177 ms 429660 KB Output is correct
57 Correct 4234 ms 465976 KB Output is correct
58 Correct 4216 ms 504940 KB Output is correct
59 Correct 4180 ms 547056 KB Output is correct
60 Correct 4120 ms 592216 KB Output is correct
61 Correct 4100 ms 640356 KB Output is correct
62 Correct 3963 ms 691468 KB Output is correct
63 Correct 3916 ms 745216 KB Output is correct
64 Correct 2188 ms 823996 KB Output is correct
65 Correct 2175 ms 823840 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 2 ms 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 632 KB Output is correct
23 Correct 2 ms 632 KB Output is correct
24 Correct 2 ms 632 KB Output is correct
25 Correct 2 ms 632 KB Output is correct
26 Correct 5 ms 1400 KB Output is correct
27 Correct 939 ms 106452 KB Output is correct
28 Correct 925 ms 106432 KB Output is correct
29 Correct 905 ms 110472 KB Output is correct
30 Correct 782 ms 110584 KB Output is correct
31 Correct 872 ms 110600 KB Output is correct
32 Correct 863 ms 110468 KB Output is correct
33 Correct 955 ms 113572 KB Output is correct
34 Correct 948 ms 113500 KB Output is correct
35 Correct 929 ms 113332 KB Output is correct
36 Correct 737 ms 113228 KB Output is correct
37 Correct 939 ms 113440 KB Output is correct
38 Correct 980 ms 117188 KB Output is correct
39 Correct 784 ms 117112 KB Output is correct
40 Correct 968 ms 117096 KB Output is correct
41 Correct 963 ms 117048 KB Output is correct
42 Correct 794 ms 119492 KB Output is correct
43 Correct 976 ms 121488 KB Output is correct
44 Correct 974 ms 121464 KB Output is correct
45 Correct 805 ms 126584 KB Output is correct
46 Correct 199 ms 22484 KB Output is correct
47 Correct 3539 ms 274876 KB Output is correct
48 Correct 3484 ms 338732 KB Output is correct
49 Correct 3509 ms 396268 KB Output is correct
50 Correct 3492 ms 396400 KB Output is correct
51 Correct 3639 ms 396244 KB Output is correct
52 Correct 4142 ms 396616 KB Output is correct
53 Correct 4119 ms 396596 KB Output is correct
54 Correct 4148 ms 396356 KB Output is correct
55 Correct 4158 ms 396312 KB Output is correct
56 Correct 4177 ms 429660 KB Output is correct
57 Correct 4234 ms 465976 KB Output is correct
58 Correct 4216 ms 504940 KB Output is correct
59 Correct 4180 ms 547056 KB Output is correct
60 Correct 4120 ms 592216 KB Output is correct
61 Correct 4100 ms 640356 KB Output is correct
62 Correct 3963 ms 691468 KB Output is correct
63 Correct 3916 ms 745216 KB Output is correct
64 Correct 2188 ms 823996 KB Output is correct
65 Correct 2175 ms 823840 KB Output is correct
66 Correct 874 ms 102520 KB Output is correct
67 Correct 6095 ms 210280 KB Output is correct
68 Correct 1384 ms 722416 KB Output is correct
69 Correct 7076 ms 723800 KB Output is correct
70 Correct 15858 ms 825384 KB Output is correct
71 Correct 12033 ms 276988 KB Output is correct
72 Correct 11754 ms 341024 KB Output is correct
73 Correct 14208 ms 398912 KB Output is correct
74 Correct 14352 ms 399228 KB Output is correct
75 Correct 14318 ms 398992 KB Output is correct
76 Correct 12634 ms 398536 KB Output is correct
77 Correct 11310 ms 398624 KB Output is correct
78 Correct 10576 ms 398428 KB Output is correct
79 Correct 14462 ms 468592 KB Output is correct
80 Correct 14371 ms 507572 KB Output is correct
81 Correct 12350 ms 549364 KB Output is correct
82 Correct 14391 ms 594944 KB Output is correct
83 Correct 12329 ms 642372 KB Output is correct
84 Correct 14240 ms 748064 KB Output is correct
85 Correct 14083 ms 826664 KB Output is correct