답안 #69484 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69484	2018-08-21T03:09:13 Z	aome	Wild Boar (JOI18_wild_boar)	C++17	12 / 100	565 ms	279528 KB

wild_boar

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;
const int L = 100005;
const int M = 4;
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	215 ms	277248 KB	Output is correct
2	Correct	215 ms	277396 KB	Output is correct
3	Correct	200 ms	277396 KB	Output is correct
4	Correct	204 ms	277432 KB	Output is correct
5	Correct	204 ms	277432 KB	Output is correct
6	Correct	199 ms	277432 KB	Output is correct
7	Correct	231 ms	277500 KB	Output is correct
8	Correct	220 ms	277500 KB	Output is correct
9	Correct	200 ms	277500 KB	Output is correct
10	Correct	229 ms	277500 KB	Output is correct
11	Correct	205 ms	277500 KB	Output is correct
12	Correct	204 ms	277600 KB	Output is correct
13	Correct	231 ms	277600 KB	Output is correct
14	Correct	208 ms	277600 KB	Output is correct
15	Correct	216 ms	277600 KB	Output is correct
16	Correct	201 ms	277648 KB	Output is correct
17	Correct	199 ms	277648 KB	Output is correct
18	Correct	203 ms	277648 KB	Output is correct
19	Correct	204 ms	277648 KB	Output is correct
20	Correct	199 ms	277648 KB	Output is correct
21	Correct	203 ms	277648 KB	Output is correct
22	Correct	225 ms	277648 KB	Output is correct
23	Correct	201 ms	277648 KB	Output is correct
24	Correct	204 ms	277648 KB	Output is correct
25	Correct	207 ms	277648 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	215 ms	277248 KB	Output is correct
2	Correct	215 ms	277396 KB	Output is correct
3	Correct	200 ms	277396 KB	Output is correct
4	Correct	204 ms	277432 KB	Output is correct
5	Correct	204 ms	277432 KB	Output is correct
6	Correct	199 ms	277432 KB	Output is correct
7	Correct	231 ms	277500 KB	Output is correct
8	Correct	220 ms	277500 KB	Output is correct
9	Correct	200 ms	277500 KB	Output is correct
10	Correct	229 ms	277500 KB	Output is correct
11	Correct	205 ms	277500 KB	Output is correct
12	Correct	204 ms	277600 KB	Output is correct
13	Correct	231 ms	277600 KB	Output is correct
14	Correct	208 ms	277600 KB	Output is correct
15	Correct	216 ms	277600 KB	Output is correct
16	Correct	201 ms	277648 KB	Output is correct
17	Correct	199 ms	277648 KB	Output is correct
18	Correct	203 ms	277648 KB	Output is correct
19	Correct	204 ms	277648 KB	Output is correct
20	Correct	199 ms	277648 KB	Output is correct
21	Correct	203 ms	277648 KB	Output is correct
22	Correct	225 ms	277648 KB	Output is correct
23	Correct	201 ms	277648 KB	Output is correct
24	Correct	204 ms	277648 KB	Output is correct
25	Correct	207 ms	277648 KB	Output is correct
26	Correct	214 ms	277648 KB	Output is correct
27	Correct	351 ms	278496 KB	Output is correct
28	Correct	344 ms	278924 KB	Output is correct
29	Incorrect	565 ms	279528 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	215 ms	277248 KB	Output is correct
2	Correct	215 ms	277396 KB	Output is correct
3	Correct	200 ms	277396 KB	Output is correct
4	Correct	204 ms	277432 KB	Output is correct
5	Correct	204 ms	277432 KB	Output is correct
6	Correct	199 ms	277432 KB	Output is correct
7	Correct	231 ms	277500 KB	Output is correct
8	Correct	220 ms	277500 KB	Output is correct
9	Correct	200 ms	277500 KB	Output is correct
10	Correct	229 ms	277500 KB	Output is correct
11	Correct	205 ms	277500 KB	Output is correct
12	Correct	204 ms	277600 KB	Output is correct
13	Correct	231 ms	277600 KB	Output is correct
14	Correct	208 ms	277600 KB	Output is correct
15	Correct	216 ms	277600 KB	Output is correct
16	Correct	201 ms	277648 KB	Output is correct
17	Correct	199 ms	277648 KB	Output is correct
18	Correct	203 ms	277648 KB	Output is correct
19	Correct	204 ms	277648 KB	Output is correct
20	Correct	199 ms	277648 KB	Output is correct
21	Correct	203 ms	277648 KB	Output is correct
22	Correct	225 ms	277648 KB	Output is correct
23	Correct	201 ms	277648 KB	Output is correct
24	Correct	204 ms	277648 KB	Output is correct
25	Correct	207 ms	277648 KB	Output is correct
26	Correct	214 ms	277648 KB	Output is correct
27	Correct	351 ms	278496 KB	Output is correct
28	Correct	344 ms	278924 KB	Output is correct
29	Incorrect	565 ms	279528 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	215 ms	277248 KB	Output is correct
2	Correct	215 ms	277396 KB	Output is correct
3	Correct	200 ms	277396 KB	Output is correct
4	Correct	204 ms	277432 KB	Output is correct
5	Correct	204 ms	277432 KB	Output is correct
6	Correct	199 ms	277432 KB	Output is correct
7	Correct	231 ms	277500 KB	Output is correct
8	Correct	220 ms	277500 KB	Output is correct
9	Correct	200 ms	277500 KB	Output is correct
10	Correct	229 ms	277500 KB	Output is correct
11	Correct	205 ms	277500 KB	Output is correct
12	Correct	204 ms	277600 KB	Output is correct
13	Correct	231 ms	277600 KB	Output is correct
14	Correct	208 ms	277600 KB	Output is correct
15	Correct	216 ms	277600 KB	Output is correct
16	Correct	201 ms	277648 KB	Output is correct
17	Correct	199 ms	277648 KB	Output is correct
18	Correct	203 ms	277648 KB	Output is correct
19	Correct	204 ms	277648 KB	Output is correct
20	Correct	199 ms	277648 KB	Output is correct
21	Correct	203 ms	277648 KB	Output is correct
22	Correct	225 ms	277648 KB	Output is correct
23	Correct	201 ms	277648 KB	Output is correct
24	Correct	204 ms	277648 KB	Output is correct
25	Correct	207 ms	277648 KB	Output is correct
26	Correct	214 ms	277648 KB	Output is correct
27	Correct	351 ms	278496 KB	Output is correct
28	Correct	344 ms	278924 KB	Output is correct
29	Incorrect	565 ms	279528 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #69484

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0