답안 #69487 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69487	2018-08-21T03:12:24 Z	aome	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	17243 ms	386620 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;
		vis[vec[i].x][vec[i].y] = 1;
		cnt1[vec[i].x]++, cnt2[vec[i].y]++;
		if (cnt1[vec[i].x] > 2 || cnt2[vec[i].y] > 2 || sz >= M) continue;
		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();

		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	248 ms	346360 KB	Output is correct
2	Correct	257 ms	346436 KB	Output is correct
3	Correct	269 ms	346468 KB	Output is correct
4	Correct	268 ms	346484 KB	Output is correct
5	Correct	253 ms	346580 KB	Output is correct
6	Correct	254 ms	346644 KB	Output is correct
7	Correct	249 ms	346656 KB	Output is correct
8	Correct	248 ms	346656 KB	Output is correct
9	Correct	243 ms	346656 KB	Output is correct
10	Correct	250 ms	346684 KB	Output is correct
11	Correct	265 ms	346684 KB	Output is correct
12	Correct	285 ms	346684 KB	Output is correct
13	Correct	295 ms	346684 KB	Output is correct
14	Correct	283 ms	346708 KB	Output is correct
15	Correct	260 ms	346708 KB	Output is correct
16	Correct	242 ms	346708 KB	Output is correct
17	Correct	247 ms	346708 KB	Output is correct
18	Correct	251 ms	346708 KB	Output is correct
19	Correct	248 ms	346708 KB	Output is correct
20	Correct	264 ms	346724 KB	Output is correct
21	Correct	255 ms	346724 KB	Output is correct
22	Correct	261 ms	346732 KB	Output is correct
23	Correct	259 ms	346732 KB	Output is correct
24	Correct	248 ms	346732 KB	Output is correct
25	Correct	245 ms	346732 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	248 ms	346360 KB	Output is correct
2	Correct	257 ms	346436 KB	Output is correct
3	Correct	269 ms	346468 KB	Output is correct
4	Correct	268 ms	346484 KB	Output is correct
5	Correct	253 ms	346580 KB	Output is correct
6	Correct	254 ms	346644 KB	Output is correct
7	Correct	249 ms	346656 KB	Output is correct
8	Correct	248 ms	346656 KB	Output is correct
9	Correct	243 ms	346656 KB	Output is correct
10	Correct	250 ms	346684 KB	Output is correct
11	Correct	265 ms	346684 KB	Output is correct
12	Correct	285 ms	346684 KB	Output is correct
13	Correct	295 ms	346684 KB	Output is correct
14	Correct	283 ms	346708 KB	Output is correct
15	Correct	260 ms	346708 KB	Output is correct
16	Correct	242 ms	346708 KB	Output is correct
17	Correct	247 ms	346708 KB	Output is correct
18	Correct	251 ms	346708 KB	Output is correct
19	Correct	248 ms	346708 KB	Output is correct
20	Correct	264 ms	346724 KB	Output is correct
21	Correct	255 ms	346724 KB	Output is correct
22	Correct	261 ms	346732 KB	Output is correct
23	Correct	259 ms	346732 KB	Output is correct
24	Correct	248 ms	346732 KB	Output is correct
25	Correct	245 ms	346732 KB	Output is correct
26	Correct	274 ms	346732 KB	Output is correct
27	Correct	453 ms	347280 KB	Output is correct
28	Correct	445 ms	347288 KB	Output is correct
29	Correct	836 ms	347680 KB	Output is correct
30	Correct	878 ms	347944 KB	Output is correct
31	Correct	881 ms	348128 KB	Output is correct
32	Correct	884 ms	348488 KB	Output is correct
33	Correct	935 ms	348708 KB	Output is correct
34	Correct	866 ms	349172 KB	Output is correct
35	Correct	685 ms	349208 KB	Output is correct
36	Correct	855 ms	349452 KB	Output is correct
37	Correct	831 ms	349828 KB	Output is correct
38	Correct	787 ms	350136 KB	Output is correct
39	Correct	879 ms	350496 KB	Output is correct
40	Correct	751 ms	350732 KB	Output is correct
41	Correct	773 ms	350964 KB	Output is correct
42	Correct	756 ms	351336 KB	Output is correct
43	Correct	745 ms	351720 KB	Output is correct
44	Correct	800 ms	352188 KB	Output is correct
45	Correct	658 ms	352364 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	248 ms	346360 KB	Output is correct
2	Correct	257 ms	346436 KB	Output is correct
3	Correct	269 ms	346468 KB	Output is correct
4	Correct	268 ms	346484 KB	Output is correct
5	Correct	253 ms	346580 KB	Output is correct
6	Correct	254 ms	346644 KB	Output is correct
7	Correct	249 ms	346656 KB	Output is correct
8	Correct	248 ms	346656 KB	Output is correct
9	Correct	243 ms	346656 KB	Output is correct
10	Correct	250 ms	346684 KB	Output is correct
11	Correct	265 ms	346684 KB	Output is correct
12	Correct	285 ms	346684 KB	Output is correct
13	Correct	295 ms	346684 KB	Output is correct
14	Correct	283 ms	346708 KB	Output is correct
15	Correct	260 ms	346708 KB	Output is correct
16	Correct	242 ms	346708 KB	Output is correct
17	Correct	247 ms	346708 KB	Output is correct
18	Correct	251 ms	346708 KB	Output is correct
19	Correct	248 ms	346708 KB	Output is correct
20	Correct	264 ms	346724 KB	Output is correct
21	Correct	255 ms	346724 KB	Output is correct
22	Correct	261 ms	346732 KB	Output is correct
23	Correct	259 ms	346732 KB	Output is correct
24	Correct	248 ms	346732 KB	Output is correct
25	Correct	245 ms	346732 KB	Output is correct
26	Correct	274 ms	346732 KB	Output is correct
27	Correct	453 ms	347280 KB	Output is correct
28	Correct	445 ms	347288 KB	Output is correct
29	Correct	836 ms	347680 KB	Output is correct
30	Correct	878 ms	347944 KB	Output is correct
31	Correct	881 ms	348128 KB	Output is correct
32	Correct	884 ms	348488 KB	Output is correct
33	Correct	935 ms	348708 KB	Output is correct
34	Correct	866 ms	349172 KB	Output is correct
35	Correct	685 ms	349208 KB	Output is correct
36	Correct	855 ms	349452 KB	Output is correct
37	Correct	831 ms	349828 KB	Output is correct
38	Correct	787 ms	350136 KB	Output is correct
39	Correct	879 ms	350496 KB	Output is correct
40	Correct	751 ms	350732 KB	Output is correct
41	Correct	773 ms	350964 KB	Output is correct
42	Correct	756 ms	351336 KB	Output is correct
43	Correct	745 ms	351720 KB	Output is correct
44	Correct	800 ms	352188 KB	Output is correct
45	Correct	658 ms	352364 KB	Output is correct
46	Correct	611 ms	352444 KB	Output is correct
47	Correct	5583 ms	356264 KB	Output is correct
48	Correct	6879 ms	356480 KB	Output is correct
49	Correct	7771 ms	356688 KB	Output is correct
50	Correct	7456 ms	356924 KB	Output is correct
51	Correct	7194 ms	357240 KB	Output is correct
52	Correct	6362 ms	357676 KB	Output is correct
53	Correct	6641 ms	357916 KB	Output is correct
54	Correct	7071 ms	358244 KB	Output is correct
55	Correct	6884 ms	358864 KB	Output is correct
56	Correct	7361 ms	359152 KB	Output is correct
57	Correct	7184 ms	359544 KB	Output is correct
58	Correct	8148 ms	360096 KB	Output is correct
59	Correct	8732 ms	360412 KB	Output is correct
60	Correct	7394 ms	360896 KB	Output is correct
61	Correct	7519 ms	361380 KB	Output is correct
62	Correct	7640 ms	361664 KB	Output is correct
63	Correct	7444 ms	362380 KB	Output is correct
64	Correct	3530 ms	362644 KB	Output is correct
65	Correct	3279 ms	363164 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	248 ms	346360 KB	Output is correct
2	Correct	257 ms	346436 KB	Output is correct
3	Correct	269 ms	346468 KB	Output is correct
4	Correct	268 ms	346484 KB	Output is correct
5	Correct	253 ms	346580 KB	Output is correct
6	Correct	254 ms	346644 KB	Output is correct
7	Correct	249 ms	346656 KB	Output is correct
8	Correct	248 ms	346656 KB	Output is correct
9	Correct	243 ms	346656 KB	Output is correct
10	Correct	250 ms	346684 KB	Output is correct
11	Correct	265 ms	346684 KB	Output is correct
12	Correct	285 ms	346684 KB	Output is correct
13	Correct	295 ms	346684 KB	Output is correct
14	Correct	283 ms	346708 KB	Output is correct
15	Correct	260 ms	346708 KB	Output is correct
16	Correct	242 ms	346708 KB	Output is correct
17	Correct	247 ms	346708 KB	Output is correct
18	Correct	251 ms	346708 KB	Output is correct
19	Correct	248 ms	346708 KB	Output is correct
20	Correct	264 ms	346724 KB	Output is correct
21	Correct	255 ms	346724 KB	Output is correct
22	Correct	261 ms	346732 KB	Output is correct
23	Correct	259 ms	346732 KB	Output is correct
24	Correct	248 ms	346732 KB	Output is correct
25	Correct	245 ms	346732 KB	Output is correct
26	Correct	274 ms	346732 KB	Output is correct
27	Correct	453 ms	347280 KB	Output is correct
28	Correct	445 ms	347288 KB	Output is correct
29	Correct	836 ms	347680 KB	Output is correct
30	Correct	878 ms	347944 KB	Output is correct
31	Correct	881 ms	348128 KB	Output is correct
32	Correct	884 ms	348488 KB	Output is correct
33	Correct	935 ms	348708 KB	Output is correct
34	Correct	866 ms	349172 KB	Output is correct
35	Correct	685 ms	349208 KB	Output is correct
36	Correct	855 ms	349452 KB	Output is correct
37	Correct	831 ms	349828 KB	Output is correct
38	Correct	787 ms	350136 KB	Output is correct
39	Correct	879 ms	350496 KB	Output is correct
40	Correct	751 ms	350732 KB	Output is correct
41	Correct	773 ms	350964 KB	Output is correct
42	Correct	756 ms	351336 KB	Output is correct
43	Correct	745 ms	351720 KB	Output is correct
44	Correct	800 ms	352188 KB	Output is correct
45	Correct	658 ms	352364 KB	Output is correct
46	Correct	611 ms	352444 KB	Output is correct
47	Correct	5583 ms	356264 KB	Output is correct
48	Correct	6879 ms	356480 KB	Output is correct
49	Correct	7771 ms	356688 KB	Output is correct
50	Correct	7456 ms	356924 KB	Output is correct
51	Correct	7194 ms	357240 KB	Output is correct
52	Correct	6362 ms	357676 KB	Output is correct
53	Correct	6641 ms	357916 KB	Output is correct
54	Correct	7071 ms	358244 KB	Output is correct
55	Correct	6884 ms	358864 KB	Output is correct
56	Correct	7361 ms	359152 KB	Output is correct
57	Correct	7184 ms	359544 KB	Output is correct
58	Correct	8148 ms	360096 KB	Output is correct
59	Correct	8732 ms	360412 KB	Output is correct
60	Correct	7394 ms	360896 KB	Output is correct
61	Correct	7519 ms	361380 KB	Output is correct
62	Correct	7640 ms	361664 KB	Output is correct
63	Correct	7444 ms	362380 KB	Output is correct
64	Correct	3530 ms	362644 KB	Output is correct
65	Correct	3279 ms	363164 KB	Output is correct
66	Correct	737 ms	363164 KB	Output is correct
67	Correct	2565 ms	363164 KB	Output is correct
68	Correct	2174 ms	363864 KB	Output is correct
69	Correct	4014 ms	364900 KB	Output is correct
70	Correct	8355 ms	366692 KB	Output is correct
71	Correct	14448 ms	369008 KB	Output is correct
72	Correct	16971 ms	369960 KB	Output is correct
73	Correct	15973 ms	371568 KB	Output is correct
74	Correct	14851 ms	373080 KB	Output is correct
75	Correct	15639 ms	374240 KB	Output is correct
76	Correct	16402 ms	375092 KB	Output is correct
77	Correct	17243 ms	376312 KB	Output is correct
78	Correct	13745 ms	377196 KB	Output is correct
79	Correct	15148 ms	378732 KB	Output is correct
80	Correct	15088 ms	380172 KB	Output is correct
81	Correct	16488 ms	380964 KB	Output is correct
82	Correct	15172 ms	382548 KB	Output is correct
83	Correct	16285 ms	383412 KB	Output is correct
84	Correct	13885 ms	384968 KB	Output is correct
85	Correct	9900 ms	386620 KB	Output is correct

답안 #69487

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