답안 #524446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524446	2022-02-09T08:38:07 Z	Sohsoh84	Wild Boar (JOI18_wild_boar)	C++17	62 / 100	8553 ms	285976 KB

wild_boar

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 2e3 + 10; // 1e5 ?
const ll MAXL = 1e5 + 10;
const ll INF = 4e18;

vector<int> adj[MAXN];
int from[MAXN], to[MAXN], n, m, t, l, sup_list[MAXL];
ll dist[MAXN][3][MAXN][3], w[MAXN], ans[2][MAXN << 2];

inline int f(int ind, int v) {
	return from[ind] + to[ind] - v;
}

inline int edge_side(int ind, int v) {
	return from[ind] == v ? 0 : 1;
}

inline void dijkstra(int tv, int tstate) {
	dist[tv][tstate][tv][tstate] = 0;
	priority_queue<plll, vector<plll>, greater<plll>> pq;
	pq.push({0, {tv, tstate}});

	while (!pq.empty()) {
		int fv = pq.top().Y.X, fstate = pq.top().Y.Y;
		ll d_v = pq.top().X;
		pq.pop();
		if (d_v != dist[tv][tstate][fv][fstate]) continue; 
	
		int lst = fv, v = 0;
		if (fstate == 0) v = from[lst];
		else if (fstate == 1) v = to[lst];
		else v = lst, lst = -1;

		for (int ind : adj[v]) {
			if (ind == lst) continue;
			int u = f(ind, v), state = edge_side(ind, u);
			ll d_u = d_v + w[ind];

			if (d_u < dist[tv][tstate][ind][state]) {
				dist[tv][tstate][ind][state] = d_u;
				pq.push({d_u, {ind, state}});
			}
		}
	}
}

inline vector<pll> v_states(int v) {
	vector<pll> ans;
	for (int ind : adj[v])
		ans.push_back({ind, edge_side(ind, v)});
	return ans;
}

inline void majik(pair<plll, plll>& a, plll b) {
	if (b.X < a.X.X) {
		a.Y = a.X;
		a.X = b;
	} else if (b.X < a.Y.X) a.Y = b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> t >> l;
	for (int i = 1; i <= m; i++) {
		cin >> from[i] >> to[i] >> w[i];
		adj[from[i]].push_back(i);
		adj[to[i]].push_back(i);
	}

	for (int i = 0; i < MAXN; i++)
		for (int j = 0; j < 3; j++)
			for (int a = 0; a < MAXN; a++)
				for (int b = 0; b < 3; b++)
					dist[i][j][a][b] = INF;

	for (int v = 1; v <= n; v++)
			dijkstra(v, 2);
	for (int i = 1; i <= m; i++)
		dijkstra(i, 1), dijkstra(i, 0);

	for (int i = 1; i <= l; i++) cin >> sup_list[i];
	while (t--) {
		int p, c;
		cin >> p >> c;
		sup_list[p] = c;
	}

	ans[1][0] = 0; // !!!
	ll fans = INF;
	
	for (int i = 2; i <= l; i++) {
		vector<pll> B = v_states(sup_list[i]);
		pair<plll, plll> A = {{INF, {INF, INF}}, {INF, {INF, INF}}};
	
		int ind = i & 1;
		if (i == 2) A.X = {0, {sup_list[i - 1], 2}};
		else {
			vector<pll> tmp = v_states(sup_list[i - 1]);
			for (int i = 0; i < int(tmp.size()); i++)
				majik(A, {ans[ind ^ 1][i], tmp[i]});
		}

		fill(ans[ind], ans[ind] + int(B.size()), INF);

		fans = INF;
		for (int i = 0; i < int(B.size()); i++) {
			if (A.X.X < INF) ans[ind][i] = min(ans[ind][i], A.X.X + dist[A.X.Y.X][A.X.Y.Y][B[i].X][B[i].Y]);
			if (A.Y.X < INF) ans[ind][i] = min(ans[ind][i], A.Y.X + dist[A.Y.Y.X][A.Y.Y.Y][B[i].X][B[i].Y]);
			fans = min(fans, ans[ind][i]);
		}
/*
		if (i == 3) {
			for (pll e : B)
				cerr << e.X << sep << e.Y << endl;
			debug(ans[ind][1])
		}
*/	}

	cout << (fans == INF ? -1 : fans) << endl;
	return 0;	
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	284944 KB	Output is correct
2	Correct	122 ms	284988 KB	Output is correct
3	Correct	113 ms	284888 KB	Output is correct
4	Correct	112 ms	284892 KB	Output is correct
5	Correct	125 ms	284992 KB	Output is correct
6	Correct	116 ms	284996 KB	Output is correct
7	Correct	115 ms	284932 KB	Output is correct
8	Correct	116 ms	284896 KB	Output is correct
9	Correct	115 ms	284968 KB	Output is correct
10	Correct	118 ms	285064 KB	Output is correct
11	Correct	114 ms	284884 KB	Output is correct
12	Correct	115 ms	284868 KB	Output is correct
13	Correct	113 ms	284996 KB	Output is correct
14	Correct	124 ms	284944 KB	Output is correct
15	Correct	115 ms	284964 KB	Output is correct
16	Correct	126 ms	284868 KB	Output is correct
17	Correct	116 ms	284928 KB	Output is correct
18	Correct	115 ms	284872 KB	Output is correct
19	Correct	115 ms	284968 KB	Output is correct
20	Correct	115 ms	284888 KB	Output is correct
21	Correct	114 ms	284880 KB	Output is correct
22	Correct	115 ms	284996 KB	Output is correct
23	Correct	119 ms	284972 KB	Output is correct
24	Correct	119 ms	285012 KB	Output is correct
25	Correct	118 ms	284956 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	284944 KB	Output is correct
2	Correct	122 ms	284988 KB	Output is correct
3	Correct	113 ms	284888 KB	Output is correct
4	Correct	112 ms	284892 KB	Output is correct
5	Correct	125 ms	284992 KB	Output is correct
6	Correct	116 ms	284996 KB	Output is correct
7	Correct	115 ms	284932 KB	Output is correct
8	Correct	116 ms	284896 KB	Output is correct
9	Correct	115 ms	284968 KB	Output is correct
10	Correct	118 ms	285064 KB	Output is correct
11	Correct	114 ms	284884 KB	Output is correct
12	Correct	115 ms	284868 KB	Output is correct
13	Correct	113 ms	284996 KB	Output is correct
14	Correct	124 ms	284944 KB	Output is correct
15	Correct	115 ms	284964 KB	Output is correct
16	Correct	126 ms	284868 KB	Output is correct
17	Correct	116 ms	284928 KB	Output is correct
18	Correct	115 ms	284872 KB	Output is correct
19	Correct	115 ms	284968 KB	Output is correct
20	Correct	115 ms	284888 KB	Output is correct
21	Correct	114 ms	284880 KB	Output is correct
22	Correct	115 ms	284996 KB	Output is correct
23	Correct	119 ms	284972 KB	Output is correct
24	Correct	119 ms	285012 KB	Output is correct
25	Correct	118 ms	284956 KB	Output is correct
26	Correct	114 ms	284976 KB	Output is correct
27	Correct	139 ms	285548 KB	Output is correct
28	Correct	142 ms	285636 KB	Output is correct
29	Correct	204 ms	285664 KB	Output is correct
30	Correct	264 ms	285612 KB	Output is correct
31	Correct	407 ms	285616 KB	Output is correct
32	Correct	402 ms	285564 KB	Output is correct
33	Correct	211 ms	285940 KB	Output is correct
34	Correct	205 ms	285712 KB	Output is correct
35	Correct	428 ms	285564 KB	Output is correct
36	Correct	325 ms	285508 KB	Output is correct
37	Correct	202 ms	285664 KB	Output is correct
38	Correct	200 ms	285704 KB	Output is correct
39	Correct	286 ms	285752 KB	Output is correct
40	Correct	199 ms	285748 KB	Output is correct
41	Correct	193 ms	285664 KB	Output is correct
42	Correct	290 ms	285604 KB	Output is correct
43	Correct	187 ms	285752 KB	Output is correct
44	Correct	188 ms	285732 KB	Output is correct
45	Correct	152 ms	285676 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	284944 KB	Output is correct
2	Correct	122 ms	284988 KB	Output is correct
3	Correct	113 ms	284888 KB	Output is correct
4	Correct	112 ms	284892 KB	Output is correct
5	Correct	125 ms	284992 KB	Output is correct
6	Correct	116 ms	284996 KB	Output is correct
7	Correct	115 ms	284932 KB	Output is correct
8	Correct	116 ms	284896 KB	Output is correct
9	Correct	115 ms	284968 KB	Output is correct
10	Correct	118 ms	285064 KB	Output is correct
11	Correct	114 ms	284884 KB	Output is correct
12	Correct	115 ms	284868 KB	Output is correct
13	Correct	113 ms	284996 KB	Output is correct
14	Correct	124 ms	284944 KB	Output is correct
15	Correct	115 ms	284964 KB	Output is correct
16	Correct	126 ms	284868 KB	Output is correct
17	Correct	116 ms	284928 KB	Output is correct
18	Correct	115 ms	284872 KB	Output is correct
19	Correct	115 ms	284968 KB	Output is correct
20	Correct	115 ms	284888 KB	Output is correct
21	Correct	114 ms	284880 KB	Output is correct
22	Correct	115 ms	284996 KB	Output is correct
23	Correct	119 ms	284972 KB	Output is correct
24	Correct	119 ms	285012 KB	Output is correct
25	Correct	118 ms	284956 KB	Output is correct
26	Correct	114 ms	284976 KB	Output is correct
27	Correct	139 ms	285548 KB	Output is correct
28	Correct	142 ms	285636 KB	Output is correct
29	Correct	204 ms	285664 KB	Output is correct
30	Correct	264 ms	285612 KB	Output is correct
31	Correct	407 ms	285616 KB	Output is correct
32	Correct	402 ms	285564 KB	Output is correct
33	Correct	211 ms	285940 KB	Output is correct
34	Correct	205 ms	285712 KB	Output is correct
35	Correct	428 ms	285564 KB	Output is correct
36	Correct	325 ms	285508 KB	Output is correct
37	Correct	202 ms	285664 KB	Output is correct
38	Correct	200 ms	285704 KB	Output is correct
39	Correct	286 ms	285752 KB	Output is correct
40	Correct	199 ms	285748 KB	Output is correct
41	Correct	193 ms	285664 KB	Output is correct
42	Correct	290 ms	285604 KB	Output is correct
43	Correct	187 ms	285752 KB	Output is correct
44	Correct	188 ms	285732 KB	Output is correct
45	Correct	152 ms	285676 KB	Output is correct
46	Correct	302 ms	285044 KB	Output is correct
47	Correct	8553 ms	285976 KB	Output is correct
48	Correct	7790 ms	285772 KB	Output is correct
49	Correct	5946 ms	285748 KB	Output is correct
50	Correct	6638 ms	285756 KB	Output is correct
51	Correct	7889 ms	285768 KB	Output is correct
52	Correct	3463 ms	285944 KB	Output is correct
53	Correct	3266 ms	285888 KB	Output is correct
54	Correct	3286 ms	285888 KB	Output is correct
55	Correct	3337 ms	285892 KB	Output is correct
56	Correct	3310 ms	285888 KB	Output is correct
57	Correct	3282 ms	285960 KB	Output is correct
58	Correct	3306 ms	285884 KB	Output is correct
59	Correct	3257 ms	285852 KB	Output is correct
60	Correct	3212 ms	285852 KB	Output is correct
61	Correct	3144 ms	285852 KB	Output is correct
62	Correct	2983 ms	285832 KB	Output is correct
63	Correct	2831 ms	285836 KB	Output is correct
64	Correct	1058 ms	285892 KB	Output is correct
65	Correct	1059 ms	285824 KB	Output is correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	284944 KB	Output is correct
2	Correct	122 ms	284988 KB	Output is correct
3	Correct	113 ms	284888 KB	Output is correct
4	Correct	112 ms	284892 KB	Output is correct
5	Correct	125 ms	284992 KB	Output is correct
6	Correct	116 ms	284996 KB	Output is correct
7	Correct	115 ms	284932 KB	Output is correct
8	Correct	116 ms	284896 KB	Output is correct
9	Correct	115 ms	284968 KB	Output is correct
10	Correct	118 ms	285064 KB	Output is correct
11	Correct	114 ms	284884 KB	Output is correct
12	Correct	115 ms	284868 KB	Output is correct
13	Correct	113 ms	284996 KB	Output is correct
14	Correct	124 ms	284944 KB	Output is correct
15	Correct	115 ms	284964 KB	Output is correct
16	Correct	126 ms	284868 KB	Output is correct
17	Correct	116 ms	284928 KB	Output is correct
18	Correct	115 ms	284872 KB	Output is correct
19	Correct	115 ms	284968 KB	Output is correct
20	Correct	115 ms	284888 KB	Output is correct
21	Correct	114 ms	284880 KB	Output is correct
22	Correct	115 ms	284996 KB	Output is correct
23	Correct	119 ms	284972 KB	Output is correct
24	Correct	119 ms	285012 KB	Output is correct
25	Correct	118 ms	284956 KB	Output is correct
26	Correct	114 ms	284976 KB	Output is correct
27	Correct	139 ms	285548 KB	Output is correct
28	Correct	142 ms	285636 KB	Output is correct
29	Correct	204 ms	285664 KB	Output is correct
30	Correct	264 ms	285612 KB	Output is correct
31	Correct	407 ms	285616 KB	Output is correct
32	Correct	402 ms	285564 KB	Output is correct
33	Correct	211 ms	285940 KB	Output is correct
34	Correct	205 ms	285712 KB	Output is correct
35	Correct	428 ms	285564 KB	Output is correct
36	Correct	325 ms	285508 KB	Output is correct
37	Correct	202 ms	285664 KB	Output is correct
38	Correct	200 ms	285704 KB	Output is correct
39	Correct	286 ms	285752 KB	Output is correct
40	Correct	199 ms	285748 KB	Output is correct
41	Correct	193 ms	285664 KB	Output is correct
42	Correct	290 ms	285604 KB	Output is correct
43	Correct	187 ms	285752 KB	Output is correct
44	Correct	188 ms	285732 KB	Output is correct
45	Correct	152 ms	285676 KB	Output is correct
46	Correct	302 ms	285044 KB	Output is correct
47	Correct	8553 ms	285976 KB	Output is correct
48	Correct	7790 ms	285772 KB	Output is correct
49	Correct	5946 ms	285748 KB	Output is correct
50	Correct	6638 ms	285756 KB	Output is correct
51	Correct	7889 ms	285768 KB	Output is correct
52	Correct	3463 ms	285944 KB	Output is correct
53	Correct	3266 ms	285888 KB	Output is correct
54	Correct	3286 ms	285888 KB	Output is correct
55	Correct	3337 ms	285892 KB	Output is correct
56	Correct	3310 ms	285888 KB	Output is correct
57	Correct	3282 ms	285960 KB	Output is correct
58	Correct	3306 ms	285884 KB	Output is correct
59	Correct	3257 ms	285852 KB	Output is correct
60	Correct	3212 ms	285852 KB	Output is correct
61	Correct	3144 ms	285852 KB	Output is correct
62	Correct	2983 ms	285832 KB	Output is correct
63	Correct	2831 ms	285836 KB	Output is correct
64	Correct	1058 ms	285892 KB	Output is correct
65	Correct	1059 ms	285824 KB	Output is correct
66	Incorrect	150 ms	285632 KB	Output isn't correct
67	Halted	0 ms	0 KB	-

답안 #524446

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 38.0