답안 #69493 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69493	2018-08-21T03:42:33 Z	aome	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	16771 ms	353080 KB

wild_boar

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;
const int L = 100005;
const int M = 5;
const long long INF = 1e18;

struct Edge {
	int w, to, id;
};

struct F {
	long long w; int x, y;

	F() { w = INF, x = y = 0; }

	F(long w, int x, int y) : w(w), x(x), y(y) {}

	bool operator < (const F& rhs) const {
		return w < rhs.w;
	}

	void dbg() { cout << "#F " << w << ' ' << x << ' ' << y << '\n';}
};

struct Data { F a[M]; };

struct State {
	long long w; int u, x, y;

	bool operator < (const State& rhs) const {
		return w > rhs.w;
	}
};

int n, m, l, q;
int arr[L];
int cnt1[N], cnt2[N];
bool vis[N][N];
Data d[N][N];
vector<Edge> G[N];

int add(vector<F>& vec, Data& cur, int pos = -1) {
	int sz = 0, ret = -1;
	for (int i = 0; i < vec.size(); ++i) {
		if (vis[vec[i].x][vec[i].y]) continue;
		if (cnt1[vec[i].x] == 2 || cnt2[vec[i].y] == 2 || sz == M) continue;
		vis[vec[i].x][vec[i].y] = 1;
		cnt1[vec[i].x]++, cnt2[vec[i].y]++;
		if (i == pos) ret = sz; cur.a[sz++] = vec[i];
	}
	for (auto i : vec) cnt1[i.x] = cnt2[i.y] = vis[i.x][i.y] = 0;
	return ret;
}

struct SegmentTree {
	Data T[L << 2];

	#define mid ((l + r) >> 1)

	Data merge(Data &x, Data &y, Data &z) {
		Data ret;
		vector<F> vec;
		for (int i = 0; i < M; ++i) {
			for (int j = 0; j < M; ++j) {
				for (int k = 0; k < M; ++k) {
					long long w = min(INF, x.a[i].w + y.a[j].w + z.a[k].w);
					if (x.a[i].y == z.a[k].x || z.a[k].y == y.a[j].x) continue;
					int L = x.a[i].x; if (L == 0) L = z.a[k].x;
					int R = y.a[j].y; if (R == 0) R = z.a[k].y;
					vec.push_back({w, L, R});
				}
			}
		}
		sort(vec.begin(), vec.end());
		add(vec, ret);
		return ret;
	}

	void build(int i, int l, int r) {
		if (l == r) { T[i].a[0].w = 0; return; }
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T[i] = merge(T[i << 1], T[i << 1 | 1], d[arr[mid]][arr[mid + 1]]);

		// cout << l << ' ' << r << '\n';
		// for (int j = 0; j < M; ++j) T[i].a[j].dbg();
	}

	void upd(int i, int l, int r, int p, int x) {
		if (l == r) { arr[l] = x; return; }
		if (mid >= p) upd(i << 1, l, mid, p, x);
		else upd(i << 1 | 1, mid + 1, r, p, x);
		T[i] = merge(T[i << 1], T[i << 1 | 1], d[arr[mid]][arr[mid + 1]]);

		// cout << l << ' ' << r << '\n';
		// for (int j = 0; j < M; ++j) T[i].a[j].dbg();
	}

	#undef mid
} IT;

void cal(int r) {
	priority_queue<State> pq;
	d[r][r].a[0].w = 0, pq.push({0, r, 0, 0});

	while (pq.size()) {
		long long W = pq.top().w;
		int u = pq.top().u, x = pq.top().x, y = pq.top().y;
		pq.pop();

		bool found = 0;
		for (int i = 0; i < M; ++i) {
			found |= d[r][u].a[i].w == W && d[r][u].a[i].x == x && d[r][u].a[i].y == y;
		}
		if (!found) continue;

		for (auto i : G[u]) {
			int w = i.w, v = i.to, id = i.id;
			if (y == id) continue;

			int L = x, R = id;
			if (L == 0) L = id;
			
			int pos = -1;
			vector<F> vec;
			for (int j = 0; j < M; ++j) {
				if (d[r][v].a[j].w > W + w && pos == -1) {
					pos = vec.size(), vec.push_back({W + w, L, R});
				}
				vec.push_back(d[r][v].a[j]);
			}
			
			int tmp = add(vec, d[r][v], pos);
			if (tmp != -1) pq.push({d[r][v].a[tmp].w, v, L, R});
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q >> l;
	for (int i = 1; i <= m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back({w, v, i});
		G[v].push_back({w, u, i});
	}

	for (int i = 1; i <= n; ++i) cal(i);

	// for (int i = 1; i <= n; ++i) {
	// 	cout << "#from " << i << '\n';
	// 	for (int j = 1; j <= n; ++j) {
	// 		cout << "#to " << j << '\n';
	// 		for (int k = 0; k < M; ++k) {
	// 			d[i][j].a[k].dbg();
	// 		}
	// 	}
	// 	cout << '\n';
	// }

	for (int i = 1; i <= l; ++i) cin >> arr[i];
	IT.build(1, 1, l);

	while (q--) {
		int p, x; cin >> p >> x;
		IT.upd(1, 1, l, p, x);
		long long res = IT.T[1].a[0].w;
		cout << (res == INF ? -1 : res) << '\n';
	}
}

Compilation message

wild_boar.cpp: In function 'int add(std::vector<F>&, Data&, int)':
wild_boar.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); ++i) {
                  ~~^~~~~~~~~~~~
wild_boar.cpp:52:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (i == pos) ret = sz; cur.a[sz++] = vec[i];
   ^~
wild_boar.cpp:52:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if (i == pos) ret = sz; cur.a[sz++] = vec[i];
                           ^~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	263 ms	346448 KB	Output is correct
2	Correct	253 ms	346468 KB	Output is correct
3	Correct	257 ms	346508 KB	Output is correct
4	Correct	256 ms	346544 KB	Output is correct
5	Correct	253 ms	346564 KB	Output is correct
6	Correct	260 ms	346596 KB	Output is correct
7	Correct	251 ms	346596 KB	Output is correct
8	Correct	267 ms	346600 KB	Output is correct
9	Correct	269 ms	346736 KB	Output is correct
10	Correct	263 ms	346736 KB	Output is correct
11	Correct	272 ms	346860 KB	Output is correct
12	Correct	303 ms	346860 KB	Output is correct
13	Correct	278 ms	346860 KB	Output is correct
14	Correct	259 ms	346860 KB	Output is correct
15	Correct	269 ms	346860 KB	Output is correct
16	Correct	266 ms	346860 KB	Output is correct
17	Correct	266 ms	346860 KB	Output is correct
18	Correct	256 ms	346860 KB	Output is correct
19	Correct	250 ms	346860 KB	Output is correct
20	Correct	268 ms	346860 KB	Output is correct
21	Correct	275 ms	346860 KB	Output is correct
22	Correct	278 ms	346860 KB	Output is correct
23	Correct	260 ms	346860 KB	Output is correct
24	Correct	260 ms	346860 KB	Output is correct
25	Correct	258 ms	346860 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	263 ms	346448 KB	Output is correct
2	Correct	253 ms	346468 KB	Output is correct
3	Correct	257 ms	346508 KB	Output is correct
4	Correct	256 ms	346544 KB	Output is correct
5	Correct	253 ms	346564 KB	Output is correct
6	Correct	260 ms	346596 KB	Output is correct
7	Correct	251 ms	346596 KB	Output is correct
8	Correct	267 ms	346600 KB	Output is correct
9	Correct	269 ms	346736 KB	Output is correct
10	Correct	263 ms	346736 KB	Output is correct
11	Correct	272 ms	346860 KB	Output is correct
12	Correct	303 ms	346860 KB	Output is correct
13	Correct	278 ms	346860 KB	Output is correct
14	Correct	259 ms	346860 KB	Output is correct
15	Correct	269 ms	346860 KB	Output is correct
16	Correct	266 ms	346860 KB	Output is correct
17	Correct	266 ms	346860 KB	Output is correct
18	Correct	256 ms	346860 KB	Output is correct
19	Correct	250 ms	346860 KB	Output is correct
20	Correct	268 ms	346860 KB	Output is correct
21	Correct	275 ms	346860 KB	Output is correct
22	Correct	278 ms	346860 KB	Output is correct
23	Correct	260 ms	346860 KB	Output is correct
24	Correct	260 ms	346860 KB	Output is correct
25	Correct	258 ms	346860 KB	Output is correct
26	Correct	254 ms	346860 KB	Output is correct
27	Correct	457 ms	347280 KB	Output is correct
28	Correct	446 ms	347360 KB	Output is correct
29	Correct	925 ms	347768 KB	Output is correct
30	Correct	818 ms	347768 KB	Output is correct
31	Correct	784 ms	347780 KB	Output is correct
32	Correct	838 ms	347780 KB	Output is correct
33	Correct	921 ms	347900 KB	Output is correct
34	Correct	828 ms	347900 KB	Output is correct
35	Correct	769 ms	347900 KB	Output is correct
36	Correct	903 ms	347900 KB	Output is correct
37	Correct	821 ms	347900 KB	Output is correct
38	Correct	779 ms	347900 KB	Output is correct
39	Correct	865 ms	347900 KB	Output is correct
40	Correct	822 ms	347900 KB	Output is correct
41	Correct	845 ms	347900 KB	Output is correct
42	Correct	846 ms	347900 KB	Output is correct
43	Correct	809 ms	347900 KB	Output is correct
44	Correct	790 ms	347900 KB	Output is correct
45	Correct	616 ms	347900 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	263 ms	346448 KB	Output is correct
2	Correct	253 ms	346468 KB	Output is correct
3	Correct	257 ms	346508 KB	Output is correct
4	Correct	256 ms	346544 KB	Output is correct
5	Correct	253 ms	346564 KB	Output is correct
6	Correct	260 ms	346596 KB	Output is correct
7	Correct	251 ms	346596 KB	Output is correct
8	Correct	267 ms	346600 KB	Output is correct
9	Correct	269 ms	346736 KB	Output is correct
10	Correct	263 ms	346736 KB	Output is correct
11	Correct	272 ms	346860 KB	Output is correct
12	Correct	303 ms	346860 KB	Output is correct
13	Correct	278 ms	346860 KB	Output is correct
14	Correct	259 ms	346860 KB	Output is correct
15	Correct	269 ms	346860 KB	Output is correct
16	Correct	266 ms	346860 KB	Output is correct
17	Correct	266 ms	346860 KB	Output is correct
18	Correct	256 ms	346860 KB	Output is correct
19	Correct	250 ms	346860 KB	Output is correct
20	Correct	268 ms	346860 KB	Output is correct
21	Correct	275 ms	346860 KB	Output is correct
22	Correct	278 ms	346860 KB	Output is correct
23	Correct	260 ms	346860 KB	Output is correct
24	Correct	260 ms	346860 KB	Output is correct
25	Correct	258 ms	346860 KB	Output is correct
26	Correct	254 ms	346860 KB	Output is correct
27	Correct	457 ms	347280 KB	Output is correct
28	Correct	446 ms	347360 KB	Output is correct
29	Correct	925 ms	347768 KB	Output is correct
30	Correct	818 ms	347768 KB	Output is correct
31	Correct	784 ms	347780 KB	Output is correct
32	Correct	838 ms	347780 KB	Output is correct
33	Correct	921 ms	347900 KB	Output is correct
34	Correct	828 ms	347900 KB	Output is correct
35	Correct	769 ms	347900 KB	Output is correct
36	Correct	903 ms	347900 KB	Output is correct
37	Correct	821 ms	347900 KB	Output is correct
38	Correct	779 ms	347900 KB	Output is correct
39	Correct	865 ms	347900 KB	Output is correct
40	Correct	822 ms	347900 KB	Output is correct
41	Correct	845 ms	347900 KB	Output is correct
42	Correct	846 ms	347900 KB	Output is correct
43	Correct	809 ms	347900 KB	Output is correct
44	Correct	790 ms	347900 KB	Output is correct
45	Correct	616 ms	347900 KB	Output is correct
46	Correct	596 ms	347900 KB	Output is correct
47	Correct	3371 ms	351532 KB	Output is correct
48	Correct	4562 ms	351532 KB	Output is correct
49	Correct	5290 ms	351532 KB	Output is correct
50	Correct	5496 ms	351532 KB	Output is correct
51	Correct	5658 ms	351532 KB	Output is correct
52	Correct	6087 ms	351532 KB	Output is correct
53	Correct	6329 ms	351532 KB	Output is correct
54	Correct	6659 ms	351532 KB	Output is correct
55	Correct	5960 ms	351532 KB	Output is correct
56	Correct	6906 ms	351532 KB	Output is correct
57	Correct	7340 ms	351532 KB	Output is correct
58	Correct	7895 ms	351532 KB	Output is correct
59	Correct	7813 ms	351532 KB	Output is correct
60	Correct	7937 ms	351532 KB	Output is correct
61	Correct	7820 ms	351532 KB	Output is correct
62	Correct	8390 ms	351532 KB	Output is correct
63	Correct	7795 ms	351532 KB	Output is correct
64	Correct	3522 ms	351532 KB	Output is correct
65	Correct	3745 ms	351532 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	263 ms	346448 KB	Output is correct
2	Correct	253 ms	346468 KB	Output is correct
3	Correct	257 ms	346508 KB	Output is correct
4	Correct	256 ms	346544 KB	Output is correct
5	Correct	253 ms	346564 KB	Output is correct
6	Correct	260 ms	346596 KB	Output is correct
7	Correct	251 ms	346596 KB	Output is correct
8	Correct	267 ms	346600 KB	Output is correct
9	Correct	269 ms	346736 KB	Output is correct
10	Correct	263 ms	346736 KB	Output is correct
11	Correct	272 ms	346860 KB	Output is correct
12	Correct	303 ms	346860 KB	Output is correct
13	Correct	278 ms	346860 KB	Output is correct
14	Correct	259 ms	346860 KB	Output is correct
15	Correct	269 ms	346860 KB	Output is correct
16	Correct	266 ms	346860 KB	Output is correct
17	Correct	266 ms	346860 KB	Output is correct
18	Correct	256 ms	346860 KB	Output is correct
19	Correct	250 ms	346860 KB	Output is correct
20	Correct	268 ms	346860 KB	Output is correct
21	Correct	275 ms	346860 KB	Output is correct
22	Correct	278 ms	346860 KB	Output is correct
23	Correct	260 ms	346860 KB	Output is correct
24	Correct	260 ms	346860 KB	Output is correct
25	Correct	258 ms	346860 KB	Output is correct
26	Correct	254 ms	346860 KB	Output is correct
27	Correct	457 ms	347280 KB	Output is correct
28	Correct	446 ms	347360 KB	Output is correct
29	Correct	925 ms	347768 KB	Output is correct
30	Correct	818 ms	347768 KB	Output is correct
31	Correct	784 ms	347780 KB	Output is correct
32	Correct	838 ms	347780 KB	Output is correct
33	Correct	921 ms	347900 KB	Output is correct
34	Correct	828 ms	347900 KB	Output is correct
35	Correct	769 ms	347900 KB	Output is correct
36	Correct	903 ms	347900 KB	Output is correct
37	Correct	821 ms	347900 KB	Output is correct
38	Correct	779 ms	347900 KB	Output is correct
39	Correct	865 ms	347900 KB	Output is correct
40	Correct	822 ms	347900 KB	Output is correct
41	Correct	845 ms	347900 KB	Output is correct
42	Correct	846 ms	347900 KB	Output is correct
43	Correct	809 ms	347900 KB	Output is correct
44	Correct	790 ms	347900 KB	Output is correct
45	Correct	616 ms	347900 KB	Output is correct
46	Correct	596 ms	347900 KB	Output is correct
47	Correct	3371 ms	351532 KB	Output is correct
48	Correct	4562 ms	351532 KB	Output is correct
49	Correct	5290 ms	351532 KB	Output is correct
50	Correct	5496 ms	351532 KB	Output is correct
51	Correct	5658 ms	351532 KB	Output is correct
52	Correct	6087 ms	351532 KB	Output is correct
53	Correct	6329 ms	351532 KB	Output is correct
54	Correct	6659 ms	351532 KB	Output is correct
55	Correct	5960 ms	351532 KB	Output is correct
56	Correct	6906 ms	351532 KB	Output is correct
57	Correct	7340 ms	351532 KB	Output is correct
58	Correct	7895 ms	351532 KB	Output is correct
59	Correct	7813 ms	351532 KB	Output is correct
60	Correct	7937 ms	351532 KB	Output is correct
61	Correct	7820 ms	351532 KB	Output is correct
62	Correct	8390 ms	351532 KB	Output is correct
63	Correct	7795 ms	351532 KB	Output is correct
64	Correct	3522 ms	351532 KB	Output is correct
65	Correct	3745 ms	351532 KB	Output is correct
66	Correct	801 ms	351532 KB	Output is correct
67	Correct	2769 ms	351532 KB	Output is correct
68	Correct	2483 ms	351532 KB	Output is correct
69	Correct	4749 ms	351532 KB	Output is correct
70	Correct	9419 ms	351616 KB	Output is correct
71	Correct	13098 ms	352804 KB	Output is correct
72	Correct	15511 ms	352804 KB	Output is correct
73	Correct	14387 ms	353016 KB	Output is correct
74	Correct	14620 ms	353080 KB	Output is correct
75	Correct	15040 ms	353080 KB	Output is correct
76	Correct	15043 ms	353080 KB	Output is correct
77	Correct	16116 ms	353080 KB	Output is correct
78	Correct	13339 ms	353080 KB	Output is correct
79	Correct	15541 ms	353080 KB	Output is correct
80	Correct	16448 ms	353080 KB	Output is correct
81	Correct	16398 ms	353080 KB	Output is correct
82	Correct	15268 ms	353080 KB	Output is correct
83	Correct	16771 ms	353080 KB	Output is correct
84	Correct	14557 ms	353080 KB	Output is correct
85	Correct	11149 ms	353080 KB	Output is correct

답안 #69493

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