oj.uz

답안 #69490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69490 2018-08-21T03:31:06 Z aome Wild Boar (JOI18_wild_boar) C++17
12 / 100
 962 ms 347884 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], cnt3[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;
		if (cnt1[vec[i].x] == 2 || cnt2[vec[i].y] == 2 || sz == M) continue;
		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) {
	memset(cnt3, 0, sizeof cnt3);

	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();

		if (cnt3[u] > M) continue;
		++cnt3[u];

		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 259 ms 346488 KB Output is correct
2 Correct 251 ms 346504 KB Output is correct
3 Correct 283 ms 346544 KB Output is correct
4 Correct 273 ms 346600 KB Output is correct
5 Correct 339 ms 346640 KB Output is correct
6 Correct 278 ms 346680 KB Output is correct
7 Correct 269 ms 346680 KB Output is correct
8 Correct 346 ms 346680 KB Output is correct
9 Correct 291 ms 346732 KB Output is correct
10 Correct 305 ms 346732 KB Output is correct
11 Correct 304 ms 346732 KB Output is correct
12 Correct 294 ms 346732 KB Output is correct
13 Correct 266 ms 346732 KB Output is correct
14 Correct 289 ms 346732 KB Output is correct
15 Correct 263 ms 346732 KB Output is correct
16 Correct 261 ms 346732 KB Output is correct
17 Correct 261 ms 346732 KB Output is correct
18 Correct 266 ms 346732 KB Output is correct
19 Correct 258 ms 346732 KB Output is correct
20 Correct 275 ms 346780 KB Output is correct
21 Correct 309 ms 346896 KB Output is correct
22 Correct 267 ms 346896 KB Output is correct
23 Correct 291 ms 346896 KB Output is correct
24 Correct 284 ms 346896 KB Output is correct
25 Correct 274 ms 346896 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 346488 KB Output is correct
2 Correct 251 ms 346504 KB Output is correct
3 Correct 283 ms 346544 KB Output is correct
4 Correct 273 ms 346600 KB Output is correct
5 Correct 339 ms 346640 KB Output is correct
6 Correct 278 ms 346680 KB Output is correct
7 Correct 269 ms 346680 KB Output is correct
8 Correct 346 ms 346680 KB Output is correct
9 Correct 291 ms 346732 KB Output is correct
10 Correct 305 ms 346732 KB Output is correct
11 Correct 304 ms 346732 KB Output is correct
12 Correct 294 ms 346732 KB Output is correct
13 Correct 266 ms 346732 KB Output is correct
14 Correct 289 ms 346732 KB Output is correct
15 Correct 263 ms 346732 KB Output is correct
16 Correct 261 ms 346732 KB Output is correct
17 Correct 261 ms 346732 KB Output is correct
18 Correct 266 ms 346732 KB Output is correct
19 Correct 258 ms 346732 KB Output is correct
20 Correct 275 ms 346780 KB Output is correct
21 Correct 309 ms 346896 KB Output is correct
22 Correct 267 ms 346896 KB Output is correct
23 Correct 291 ms 346896 KB Output is correct
24 Correct 284 ms 346896 KB Output is correct
25 Correct 274 ms 346896 KB Output is correct
26 Correct 266 ms 346896 KB Output is correct
27 Correct 467 ms 347236 KB Output is correct
28 Correct 442 ms 347240 KB Output is correct
29 Correct 845 ms 347864 KB Output is correct
30 Correct 901 ms 347864 KB Output is correct
31 Correct 804 ms 347884 KB Output is correct
32 Correct 728 ms 347884 KB Output is correct
33 Correct 815 ms 347884 KB Output is correct
34 Correct 868 ms 347884 KB Output is correct
35 Correct 733 ms 347884 KB Output is correct
36 Correct 827 ms 347884 KB Output is correct
37 Incorrect 962 ms 347884 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 346488 KB Output is correct
2 Correct 251 ms 346504 KB Output is correct
3 Correct 283 ms 346544 KB Output is correct
4 Correct 273 ms 346600 KB Output is correct
5 Correct 339 ms 346640 KB Output is correct
6 Correct 278 ms 346680 KB Output is correct
7 Correct 269 ms 346680 KB Output is correct
8 Correct 346 ms 346680 KB Output is correct
9 Correct 291 ms 346732 KB Output is correct
10 Correct 305 ms 346732 KB Output is correct
11 Correct 304 ms 346732 KB Output is correct
12 Correct 294 ms 346732 KB Output is correct
13 Correct 266 ms 346732 KB Output is correct
14 Correct 289 ms 346732 KB Output is correct
15 Correct 263 ms 346732 KB Output is correct
16 Correct 261 ms 346732 KB Output is correct
17 Correct 261 ms 346732 KB Output is correct
18 Correct 266 ms 346732 KB Output is correct
19 Correct 258 ms 346732 KB Output is correct
20 Correct 275 ms 346780 KB Output is correct
21 Correct 309 ms 346896 KB Output is correct
22 Correct 267 ms 346896 KB Output is correct
23 Correct 291 ms 346896 KB Output is correct
24 Correct 284 ms 346896 KB Output is correct
25 Correct 274 ms 346896 KB Output is correct
26 Correct 266 ms 346896 KB Output is correct
27 Correct 467 ms 347236 KB Output is correct
28 Correct 442 ms 347240 KB Output is correct
29 Correct 845 ms 347864 KB Output is correct
30 Correct 901 ms 347864 KB Output is correct
31 Correct 804 ms 347884 KB Output is correct
32 Correct 728 ms 347884 KB Output is correct
33 Correct 815 ms 347884 KB Output is correct
34 Correct 868 ms 347884 KB Output is correct
35 Correct 733 ms 347884 KB Output is correct
36 Correct 827 ms 347884 KB Output is correct
37 Incorrect 962 ms 347884 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 346488 KB Output is correct
2 Correct 251 ms 346504 KB Output is correct
3 Correct 283 ms 346544 KB Output is correct
4 Correct 273 ms 346600 KB Output is correct
5 Correct 339 ms 346640 KB Output is correct
6 Correct 278 ms 346680 KB Output is correct
7 Correct 269 ms 346680 KB Output is correct
8 Correct 346 ms 346680 KB Output is correct
9 Correct 291 ms 346732 KB Output is correct
10 Correct 305 ms 346732 KB Output is correct
11 Correct 304 ms 346732 KB Output is correct
12 Correct 294 ms 346732 KB Output is correct
13 Correct 266 ms 346732 KB Output is correct
14 Correct 289 ms 346732 KB Output is correct
15 Correct 263 ms 346732 KB Output is correct
16 Correct 261 ms 346732 KB Output is correct
17 Correct 261 ms 346732 KB Output is correct
18 Correct 266 ms 346732 KB Output is correct
19 Correct 258 ms 346732 KB Output is correct
20 Correct 275 ms 346780 KB Output is correct
21 Correct 309 ms 346896 KB Output is correct
22 Correct 267 ms 346896 KB Output is correct
23 Correct 291 ms 346896 KB Output is correct
24 Correct 284 ms 346896 KB Output is correct
25 Correct 274 ms 346896 KB Output is correct
26 Correct 266 ms 346896 KB Output is correct
27 Correct 467 ms 347236 KB Output is correct
28 Correct 442 ms 347240 KB Output is correct
29 Correct 845 ms 347864 KB Output is correct
30 Correct 901 ms 347864 KB Output is correct
31 Correct 804 ms 347884 KB Output is correct
32 Correct 728 ms 347884 KB Output is correct
33 Correct 815 ms 347884 KB Output is correct
34 Correct 868 ms 347884 KB Output is correct
35 Correct 733 ms 347884 KB Output is correct
36 Correct 827 ms 347884 KB Output is correct
37 Incorrect 962 ms 347884 KB Output isn't correct
38 Halted 0 ms 0 KB -