Submission #77845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
77845	2018-09-30T18:50:10 Z	tmwilliamlin168	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	10053 ms	536676 KB

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][5], st[1<<18][5];
priority_queue<a<ll, 4>, vector<a<ll, 4>>, greater<a<ll, 4>>> pq;

bool ad(a<ll, 3> b[5], a<ll, 3> c, int d) {
	int i=0, c1=0, c2=0, c3=0;
	while(i<d&&b[i][0]<INF) {
		c1+=b[i][1]==c[1]&&b[i][2]==c[2];
		c2+=b[i][1]==c[1];
		c3+=b[i][2]==c[2];
		++i;
	}
	if(i<5&&!c1&&c2<2&&c3<2) {
		b[i]=min(c, b[i]);
		return 1;
	}
	return 0;
}

void dij(int s, a<ll, 3> d[mxN][5]) {
	for(int i=0; i<n; ++i)
		for(int j=0; j<5; ++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();
		if(!ad(d[u[1]], {u[0], u[2], u[3]}, 5))
			continue;
		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<5; ++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);
	for(int j=0; j<5; ++j) {
		st[i][j]={INF};
		for(int k=0; k<5; ++k)
			for(int l=0; l<5; ++l)
				if(st[2*i][k][2]!=st[2*i+1][l][1])
					ad(st[i], {st[2*i][k][0]+st[2*i+1][l][0], st[2*i][k][1], st[2*i+1][l][2]}, 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], st[1][4][0]});
		cout << (ans>=INF?-1:ans) << "\n";
	}
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	2 ms	544 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	2 ms	612 KB	Output is correct
7	Correct	2 ms	612 KB	Output is correct
8	Correct	2 ms	612 KB	Output is correct
9	Correct	2 ms	612 KB	Output is correct
10	Correct	2 ms	656 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	2 ms	656 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	2 ms	696 KB	Output is correct
16	Correct	2 ms	696 KB	Output is correct
17	Correct	2 ms	700 KB	Output is correct
18	Correct	2 ms	700 KB	Output is correct
19	Correct	2 ms	736 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	736 KB	Output is correct
22	Correct	2 ms	736 KB	Output is correct
23	Correct	2 ms	736 KB	Output is correct
24	Correct	2 ms	736 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct

Subtask #2
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	2 ms	544 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	2 ms	612 KB	Output is correct
7	Correct	2 ms	612 KB	Output is correct
8	Correct	2 ms	612 KB	Output is correct
9	Correct	2 ms	612 KB	Output is correct
10	Correct	2 ms	656 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	2 ms	656 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	2 ms	696 KB	Output is correct
16	Correct	2 ms	696 KB	Output is correct
17	Correct	2 ms	700 KB	Output is correct
18	Correct	2 ms	700 KB	Output is correct
19	Correct	2 ms	736 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	736 KB	Output is correct
22	Correct	2 ms	736 KB	Output is correct
23	Correct	2 ms	736 KB	Output is correct
24	Correct	2 ms	736 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	5 ms	864 KB	Output is correct
27	Correct	397 ms	33400 KB	Output is correct
28	Correct	378 ms	33400 KB	Output is correct
29	Correct	1242 ms	33652 KB	Output is correct
30	Correct	1235 ms	34044 KB	Output is correct
31	Correct	1263 ms	34044 KB	Output is correct
32	Correct	1176 ms	34260 KB	Output is correct
33	Correct	1283 ms	36272 KB	Output is correct
34	Correct	1307 ms	36728 KB	Output is correct
35	Correct	1125 ms	36884 KB	Output is correct
36	Correct	1251 ms	37064 KB	Output is correct
37	Correct	1300 ms	37456 KB	Output is correct
38	Correct	1211 ms	40040 KB	Output is correct
39	Correct	1263 ms	40316 KB	Output is correct
40	Correct	1209 ms	40516 KB	Output is correct
41	Correct	1217 ms	40956 KB	Output is correct
42	Correct	1219 ms	42904 KB	Output is correct
43	Correct	1250 ms	44276 KB	Output is correct
44	Correct	1198 ms	44616 KB	Output is correct
45	Correct	752 ms	48500 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	2 ms	544 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	2 ms	612 KB	Output is correct
7	Correct	2 ms	612 KB	Output is correct
8	Correct	2 ms	612 KB	Output is correct
9	Correct	2 ms	612 KB	Output is correct
10	Correct	2 ms	656 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	2 ms	656 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	2 ms	696 KB	Output is correct
16	Correct	2 ms	696 KB	Output is correct
17	Correct	2 ms	700 KB	Output is correct
18	Correct	2 ms	700 KB	Output is correct
19	Correct	2 ms	736 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	736 KB	Output is correct
22	Correct	2 ms	736 KB	Output is correct
23	Correct	2 ms	736 KB	Output is correct
24	Correct	2 ms	736 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	5 ms	864 KB	Output is correct
27	Correct	397 ms	33400 KB	Output is correct
28	Correct	378 ms	33400 KB	Output is correct
29	Correct	1242 ms	33652 KB	Output is correct
30	Correct	1235 ms	34044 KB	Output is correct
31	Correct	1263 ms	34044 KB	Output is correct
32	Correct	1176 ms	34260 KB	Output is correct
33	Correct	1283 ms	36272 KB	Output is correct
34	Correct	1307 ms	36728 KB	Output is correct
35	Correct	1125 ms	36884 KB	Output is correct
36	Correct	1251 ms	37064 KB	Output is correct
37	Correct	1300 ms	37456 KB	Output is correct
38	Correct	1211 ms	40040 KB	Output is correct
39	Correct	1263 ms	40316 KB	Output is correct
40	Correct	1209 ms	40516 KB	Output is correct
41	Correct	1217 ms	40956 KB	Output is correct
42	Correct	1219 ms	42904 KB	Output is correct
43	Correct	1250 ms	44276 KB	Output is correct
44	Correct	1198 ms	44616 KB	Output is correct
45	Correct	752 ms	48500 KB	Output is correct
46	Correct	153 ms	48500 KB	Output is correct
47	Correct	2918 ms	68904 KB	Output is correct
48	Correct	3523 ms	116064 KB	Output is correct
49	Correct	3740 ms	159296 KB	Output is correct
50	Correct	3753 ms	159396 KB	Output is correct
51	Correct	3836 ms	159652 KB	Output is correct
52	Correct	4100 ms	160104 KB	Output is correct
53	Correct	4184 ms	160516 KB	Output is correct
54	Correct	4089 ms	160940 KB	Output is correct
55	Correct	4157 ms	161392 KB	Output is correct
56	Correct	4199 ms	186812 KB	Output is correct
57	Correct	4396 ms	214652 KB	Output is correct
58	Correct	4502 ms	244900 KB	Output is correct
59	Correct	4449 ms	277180 KB	Output is correct
60	Correct	4366 ms	311952 KB	Output is correct
61	Correct	4388 ms	349136 KB	Output is correct
62	Correct	4194 ms	388820 KB	Output is correct
63	Correct	4134 ms	430468 KB	Output is correct
64	Correct	1741 ms	512856 KB	Output is correct
65	Correct	1692 ms	513352 KB	Output is correct

Subtask #4
38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	2 ms	544 KB	Output is correct
5	Correct	3 ms	592 KB	Output is correct
6	Correct	2 ms	612 KB	Output is correct
7	Correct	2 ms	612 KB	Output is correct
8	Correct	2 ms	612 KB	Output is correct
9	Correct	2 ms	612 KB	Output is correct
10	Correct	2 ms	656 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	656 KB	Output is correct
13	Correct	2 ms	656 KB	Output is correct
14	Correct	2 ms	656 KB	Output is correct
15	Correct	2 ms	696 KB	Output is correct
16	Correct	2 ms	696 KB	Output is correct
17	Correct	2 ms	700 KB	Output is correct
18	Correct	2 ms	700 KB	Output is correct
19	Correct	2 ms	736 KB	Output is correct
20	Correct	2 ms	736 KB	Output is correct
21	Correct	2 ms	736 KB	Output is correct
22	Correct	2 ms	736 KB	Output is correct
23	Correct	2 ms	736 KB	Output is correct
24	Correct	2 ms	736 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	5 ms	864 KB	Output is correct
27	Correct	397 ms	33400 KB	Output is correct
28	Correct	378 ms	33400 KB	Output is correct
29	Correct	1242 ms	33652 KB	Output is correct
30	Correct	1235 ms	34044 KB	Output is correct
31	Correct	1263 ms	34044 KB	Output is correct
32	Correct	1176 ms	34260 KB	Output is correct
33	Correct	1283 ms	36272 KB	Output is correct
34	Correct	1307 ms	36728 KB	Output is correct
35	Correct	1125 ms	36884 KB	Output is correct
36	Correct	1251 ms	37064 KB	Output is correct
37	Correct	1300 ms	37456 KB	Output is correct
38	Correct	1211 ms	40040 KB	Output is correct
39	Correct	1263 ms	40316 KB	Output is correct
40	Correct	1209 ms	40516 KB	Output is correct
41	Correct	1217 ms	40956 KB	Output is correct
42	Correct	1219 ms	42904 KB	Output is correct
43	Correct	1250 ms	44276 KB	Output is correct
44	Correct	1198 ms	44616 KB	Output is correct
45	Correct	752 ms	48500 KB	Output is correct
46	Correct	153 ms	48500 KB	Output is correct
47	Correct	2918 ms	68904 KB	Output is correct
48	Correct	3523 ms	116064 KB	Output is correct
49	Correct	3740 ms	159296 KB	Output is correct
50	Correct	3753 ms	159396 KB	Output is correct
51	Correct	3836 ms	159652 KB	Output is correct
52	Correct	4100 ms	160104 KB	Output is correct
53	Correct	4184 ms	160516 KB	Output is correct
54	Correct	4089 ms	160940 KB	Output is correct
55	Correct	4157 ms	161392 KB	Output is correct
56	Correct	4199 ms	186812 KB	Output is correct
57	Correct	4396 ms	214652 KB	Output is correct
58	Correct	4502 ms	244900 KB	Output is correct
59	Correct	4449 ms	277180 KB	Output is correct
60	Correct	4366 ms	311952 KB	Output is correct
61	Correct	4388 ms	349136 KB	Output is correct
62	Correct	4194 ms	388820 KB	Output is correct
63	Correct	4134 ms	430468 KB	Output is correct
64	Correct	1741 ms	512856 KB	Output is correct
65	Correct	1692 ms	513352 KB	Output is correct
66	Correct	1233 ms	513352 KB	Output is correct
67	Correct	626 ms	513352 KB	Output is correct
68	Correct	933 ms	513352 KB	Output is correct
69	Correct	1395 ms	513352 KB	Output is correct
70	Correct	2205 ms	516944 KB	Output is correct
71	Correct	8796 ms	516944 KB	Output is correct
72	Correct	9824 ms	516944 KB	Output is correct
73	Correct	9338 ms	516944 KB	Output is correct
74	Correct	9307 ms	516944 KB	Output is correct
75	Correct	9582 ms	516944 KB	Output is correct
76	Correct	10053 ms	516944 KB	Output is correct
77	Correct	9311 ms	516944 KB	Output is correct
78	Correct	7720 ms	516944 KB	Output is correct
79	Correct	9198 ms	516944 KB	Output is correct
80	Correct	9177 ms	516944 KB	Output is correct
81	Correct	9788 ms	516944 KB	Output is correct
82	Correct	8768 ms	516944 KB	Output is correct
83	Correct	9740 ms	516944 KB	Output is correct
84	Correct	8151 ms	516944 KB	Output is correct
85	Correct	5412 ms	536676 KB	Output is correct

Submission #77845

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 38.0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
38.0 / 38.0