oj.uz

Submission #69487

# Submission time Handle Problem Language Result Execution time Memory
69487 2018-08-21T03:12:24 Z aome Wild Boar (JOI18_wild_boar) C++17
100 / 100
 17243 ms 386620 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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