답안 #69495 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69495	2018-08-21T03:51:05 Z	aome	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	13279 ms	388356 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];
long long f[N][N];
bool vis[N][N];
bool memo[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;
		vector< pair<int, int> > vec2;
		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;
					f[L][R] = min(f[L][R], w);
					if (!memo[L][R]) {
						memo[L][R] = 1, vec2.push_back({L, R});
					}
				}
			}
		}
		for (auto i : vec2) {
			int L = i.first, R = i.second;
			vec.push_back({f[L][R], L, R});
			f[L][R] = INF, memo[L][R] = 0;
		}
		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];
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= m; ++j) f[i][j] = INF;
	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:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); ++i) {
                  ~~^~~~~~~~~~~~
wild_boar.cpp:54:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (i == pos) ret = sz; cur.a[sz++] = vec[i];
   ^~
wild_boar.cpp:54: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	255 ms	346448 KB	Output is correct
2	Correct	272 ms	346604 KB	Output is correct
3	Correct	301 ms	346724 KB	Output is correct
4	Correct	267 ms	346724 KB	Output is correct
5	Correct	263 ms	346724 KB	Output is correct
6	Correct	271 ms	346724 KB	Output is correct
7	Correct	299 ms	346800 KB	Output is correct
8	Correct	311 ms	346800 KB	Output is correct
9	Correct	292 ms	346800 KB	Output is correct
10	Correct	316 ms	346800 KB	Output is correct
11	Correct	314 ms	346836 KB	Output is correct
12	Correct	284 ms	346836 KB	Output is correct
13	Correct	292 ms	346836 KB	Output is correct
14	Correct	268 ms	346852 KB	Output is correct
15	Correct	317 ms	346852 KB	Output is correct
16	Correct	255 ms	346852 KB	Output is correct
17	Correct	282 ms	346852 KB	Output is correct
18	Correct	267 ms	346852 KB	Output is correct
19	Correct	282 ms	346964 KB	Output is correct
20	Correct	302 ms	346964 KB	Output is correct
21	Correct	300 ms	346964 KB	Output is correct
22	Correct	305 ms	346964 KB	Output is correct
23	Correct	281 ms	346964 KB	Output is correct
24	Correct	313 ms	346964 KB	Output is correct
25	Correct	291 ms	346964 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	255 ms	346448 KB	Output is correct
2	Correct	272 ms	346604 KB	Output is correct
3	Correct	301 ms	346724 KB	Output is correct
4	Correct	267 ms	346724 KB	Output is correct
5	Correct	263 ms	346724 KB	Output is correct
6	Correct	271 ms	346724 KB	Output is correct
7	Correct	299 ms	346800 KB	Output is correct
8	Correct	311 ms	346800 KB	Output is correct
9	Correct	292 ms	346800 KB	Output is correct
10	Correct	316 ms	346800 KB	Output is correct
11	Correct	314 ms	346836 KB	Output is correct
12	Correct	284 ms	346836 KB	Output is correct
13	Correct	292 ms	346836 KB	Output is correct
14	Correct	268 ms	346852 KB	Output is correct
15	Correct	317 ms	346852 KB	Output is correct
16	Correct	255 ms	346852 KB	Output is correct
17	Correct	282 ms	346852 KB	Output is correct
18	Correct	267 ms	346852 KB	Output is correct
19	Correct	282 ms	346964 KB	Output is correct
20	Correct	302 ms	346964 KB	Output is correct
21	Correct	300 ms	346964 KB	Output is correct
22	Correct	305 ms	346964 KB	Output is correct
23	Correct	281 ms	346964 KB	Output is correct
24	Correct	313 ms	346964 KB	Output is correct
25	Correct	291 ms	346964 KB	Output is correct
26	Correct	266 ms	346988 KB	Output is correct
27	Correct	382 ms	348012 KB	Output is correct
28	Correct	373 ms	348016 KB	Output is correct
29	Correct	627 ms	350316 KB	Output is correct
30	Correct	557 ms	350316 KB	Output is correct
31	Correct	565 ms	350316 KB	Output is correct
32	Correct	606 ms	350316 KB	Output is correct
33	Correct	719 ms	350316 KB	Output is correct
34	Correct	665 ms	350316 KB	Output is correct
35	Correct	542 ms	350316 KB	Output is correct
36	Correct	538 ms	350316 KB	Output is correct
37	Correct	674 ms	350316 KB	Output is correct
38	Correct	638 ms	350316 KB	Output is correct
39	Correct	557 ms	350316 KB	Output is correct
40	Correct	671 ms	350332 KB	Output is correct
41	Correct	746 ms	350332 KB	Output is correct
42	Correct	596 ms	350332 KB	Output is correct
43	Correct	813 ms	350332 KB	Output is correct
44	Correct	729 ms	350356 KB	Output is correct
45	Correct	484 ms	350356 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	255 ms	346448 KB	Output is correct
2	Correct	272 ms	346604 KB	Output is correct
3	Correct	301 ms	346724 KB	Output is correct
4	Correct	267 ms	346724 KB	Output is correct
5	Correct	263 ms	346724 KB	Output is correct
6	Correct	271 ms	346724 KB	Output is correct
7	Correct	299 ms	346800 KB	Output is correct
8	Correct	311 ms	346800 KB	Output is correct
9	Correct	292 ms	346800 KB	Output is correct
10	Correct	316 ms	346800 KB	Output is correct
11	Correct	314 ms	346836 KB	Output is correct
12	Correct	284 ms	346836 KB	Output is correct
13	Correct	292 ms	346836 KB	Output is correct
14	Correct	268 ms	346852 KB	Output is correct
15	Correct	317 ms	346852 KB	Output is correct
16	Correct	255 ms	346852 KB	Output is correct
17	Correct	282 ms	346852 KB	Output is correct
18	Correct	267 ms	346852 KB	Output is correct
19	Correct	282 ms	346964 KB	Output is correct
20	Correct	302 ms	346964 KB	Output is correct
21	Correct	300 ms	346964 KB	Output is correct
22	Correct	305 ms	346964 KB	Output is correct
23	Correct	281 ms	346964 KB	Output is correct
24	Correct	313 ms	346964 KB	Output is correct
25	Correct	291 ms	346964 KB	Output is correct
26	Correct	266 ms	346988 KB	Output is correct
27	Correct	382 ms	348012 KB	Output is correct
28	Correct	373 ms	348016 KB	Output is correct
29	Correct	627 ms	350316 KB	Output is correct
30	Correct	557 ms	350316 KB	Output is correct
31	Correct	565 ms	350316 KB	Output is correct
32	Correct	606 ms	350316 KB	Output is correct
33	Correct	719 ms	350316 KB	Output is correct
34	Correct	665 ms	350316 KB	Output is correct
35	Correct	542 ms	350316 KB	Output is correct
36	Correct	538 ms	350316 KB	Output is correct
37	Correct	674 ms	350316 KB	Output is correct
38	Correct	638 ms	350316 KB	Output is correct
39	Correct	557 ms	350316 KB	Output is correct
40	Correct	671 ms	350332 KB	Output is correct
41	Correct	746 ms	350332 KB	Output is correct
42	Correct	596 ms	350332 KB	Output is correct
43	Correct	813 ms	350332 KB	Output is correct
44	Correct	729 ms	350356 KB	Output is correct
45	Correct	484 ms	350356 KB	Output is correct
46	Correct	587 ms	351996 KB	Output is correct
47	Correct	3129 ms	383048 KB	Output is correct
48	Correct	4339 ms	383048 KB	Output is correct
49	Correct	5630 ms	383048 KB	Output is correct
50	Correct	5054 ms	383048 KB	Output is correct
51	Correct	4691 ms	383048 KB	Output is correct
52	Correct	6386 ms	386680 KB	Output is correct
53	Correct	5905 ms	386800 KB	Output is correct
54	Correct	6308 ms	386800 KB	Output is correct
55	Correct	6168 ms	386800 KB	Output is correct
56	Correct	6015 ms	386800 KB	Output is correct
57	Correct	6336 ms	386800 KB	Output is correct
58	Correct	7884 ms	386800 KB	Output is correct
59	Correct	7733 ms	386800 KB	Output is correct
60	Correct	7757 ms	386800 KB	Output is correct
61	Correct	8084 ms	386800 KB	Output is correct
62	Correct	8223 ms	386800 KB	Output is correct
63	Correct	8015 ms	386800 KB	Output is correct
64	Correct	3568 ms	386800 KB	Output is correct
65	Correct	3399 ms	386800 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	255 ms	346448 KB	Output is correct
2	Correct	272 ms	346604 KB	Output is correct
3	Correct	301 ms	346724 KB	Output is correct
4	Correct	267 ms	346724 KB	Output is correct
5	Correct	263 ms	346724 KB	Output is correct
6	Correct	271 ms	346724 KB	Output is correct
7	Correct	299 ms	346800 KB	Output is correct
8	Correct	311 ms	346800 KB	Output is correct
9	Correct	292 ms	346800 KB	Output is correct
10	Correct	316 ms	346800 KB	Output is correct
11	Correct	314 ms	346836 KB	Output is correct
12	Correct	284 ms	346836 KB	Output is correct
13	Correct	292 ms	346836 KB	Output is correct
14	Correct	268 ms	346852 KB	Output is correct
15	Correct	317 ms	346852 KB	Output is correct
16	Correct	255 ms	346852 KB	Output is correct
17	Correct	282 ms	346852 KB	Output is correct
18	Correct	267 ms	346852 KB	Output is correct
19	Correct	282 ms	346964 KB	Output is correct
20	Correct	302 ms	346964 KB	Output is correct
21	Correct	300 ms	346964 KB	Output is correct
22	Correct	305 ms	346964 KB	Output is correct
23	Correct	281 ms	346964 KB	Output is correct
24	Correct	313 ms	346964 KB	Output is correct
25	Correct	291 ms	346964 KB	Output is correct
26	Correct	266 ms	346988 KB	Output is correct
27	Correct	382 ms	348012 KB	Output is correct
28	Correct	373 ms	348016 KB	Output is correct
29	Correct	627 ms	350316 KB	Output is correct
30	Correct	557 ms	350316 KB	Output is correct
31	Correct	565 ms	350316 KB	Output is correct
32	Correct	606 ms	350316 KB	Output is correct
33	Correct	719 ms	350316 KB	Output is correct
34	Correct	665 ms	350316 KB	Output is correct
35	Correct	542 ms	350316 KB	Output is correct
36	Correct	538 ms	350316 KB	Output is correct
37	Correct	674 ms	350316 KB	Output is correct
38	Correct	638 ms	350316 KB	Output is correct
39	Correct	557 ms	350316 KB	Output is correct
40	Correct	671 ms	350332 KB	Output is correct
41	Correct	746 ms	350332 KB	Output is correct
42	Correct	596 ms	350332 KB	Output is correct
43	Correct	813 ms	350332 KB	Output is correct
44	Correct	729 ms	350356 KB	Output is correct
45	Correct	484 ms	350356 KB	Output is correct
46	Correct	587 ms	351996 KB	Output is correct
47	Correct	3129 ms	383048 KB	Output is correct
48	Correct	4339 ms	383048 KB	Output is correct
49	Correct	5630 ms	383048 KB	Output is correct
50	Correct	5054 ms	383048 KB	Output is correct
51	Correct	4691 ms	383048 KB	Output is correct
52	Correct	6386 ms	386680 KB	Output is correct
53	Correct	5905 ms	386800 KB	Output is correct
54	Correct	6308 ms	386800 KB	Output is correct
55	Correct	6168 ms	386800 KB	Output is correct
56	Correct	6015 ms	386800 KB	Output is correct
57	Correct	6336 ms	386800 KB	Output is correct
58	Correct	7884 ms	386800 KB	Output is correct
59	Correct	7733 ms	386800 KB	Output is correct
60	Correct	7757 ms	386800 KB	Output is correct
61	Correct	8084 ms	386800 KB	Output is correct
62	Correct	8223 ms	386800 KB	Output is correct
63	Correct	8015 ms	386800 KB	Output is correct
64	Correct	3568 ms	386800 KB	Output is correct
65	Correct	3399 ms	386800 KB	Output is correct
66	Correct	510 ms	386800 KB	Output is correct
67	Correct	2020 ms	386800 KB	Output is correct
68	Correct	2703 ms	386800 KB	Output is correct
69	Correct	4176 ms	386800 KB	Output is correct
70	Correct	6745 ms	386896 KB	Output is correct
71	Correct	6810 ms	386896 KB	Output is correct
72	Correct	9154 ms	386896 KB	Output is correct
73	Correct	12105 ms	388324 KB	Output is correct
74	Correct	11701 ms	388324 KB	Output is correct
75	Correct	11984 ms	388324 KB	Output is correct
76	Correct	9283 ms	388324 KB	Output is correct
77	Correct	8692 ms	388324 KB	Output is correct
78	Correct	7144 ms	388324 KB	Output is correct
79	Correct	13279 ms	388356 KB	Output is correct
80	Correct	12762 ms	388356 KB	Output is correct
81	Correct	10266 ms	388356 KB	Output is correct
82	Correct	12803 ms	388356 KB	Output is correct
83	Correct	10644 ms	388356 KB	Output is correct
84	Correct	13175 ms	388356 KB	Output is correct
85	Correct	7948 ms	388356 KB	Output is correct

답안 #69495

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