oj.uz

Submission #69479

# Submission time Handle Problem Language Result Execution time Memory
69479 2018-08-21T02:39:22 Z aome Wild Boar (JOI18_wild_boar) C++17
0 / 100
 381 ms 346668 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2005;
const int L = 100005;
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[5]; };

struct State {
	long long w; int u, x;

	bool operator < (const State& rhs) const {
		return w > rhs.w;
	}
};

int n, m, l, q;
int arr[L];
int cnt[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) {
		cnt[vec[i].x]++;
		if (cnt[vec[i].x] > 2 || sz >= 4) continue;
		if (i == pos) ret = sz; cur.a[sz++] = vec[i];
	}
	for (auto i : vec) cnt[i.x] = 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 < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				for (int k = 0; k < 4; ++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 < 4; ++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 < 4; ++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});

	while (pq.size()) {
		long long w = pq.top().w;
		int u = pq.top().u, x = pq.top().x;
		pq.pop();

		if (d[r][u].a[x].w != w) continue;

		for (auto i : G[u]) {
			int w = i.w, v = i.to, id = i.id;
			if (d[r][u].a[x].y == id) continue;

			int L = d[r][u].a[x].x, R = id;
			if (L == 0) L = id;
			
			int pos = -1;
			vector<F> vec;
			for (int j = 0; j < 4; ++j) {
				if (d[r][v].a[j].w > d[r][u].a[x].w + w && pos == -1) {
					pos = vec.size(), vec.push_back({d[r][u].a[x].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, tmp});
		}
	}
}

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 < 4; ++k) {
	// 			d[i][j].a[k].dbg();
	// 		}
	// 	}
	// }

	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:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); ++i) {
                  ~~^~~~~~~~~~~~
wild_boar.cpp:48:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (i == pos) ret = sz; cur.a[sz++] = vec[i];
   ^~
wild_boar.cpp:48: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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 346532 KB Output is correct
2 Correct 264 ms 346668 KB Output is correct
3 Correct 269 ms 346668 KB Output is correct
4 Correct 276 ms 346668 KB Output is correct
5 Incorrect 263 ms 346668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 346532 KB Output is correct
2 Correct 264 ms 346668 KB Output is correct
3 Correct 269 ms 346668 KB Output is correct
4 Correct 276 ms 346668 KB Output is correct
5 Incorrect 263 ms 346668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 346532 KB Output is correct
2 Correct 264 ms 346668 KB Output is correct
3 Correct 269 ms 346668 KB Output is correct
4 Correct 276 ms 346668 KB Output is correct
5 Incorrect 263 ms 346668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 346532 KB Output is correct
2 Correct 264 ms 346668 KB Output is correct
3 Correct 269 ms 346668 KB Output is correct
4 Correct 276 ms 346668 KB Output is correct
5 Incorrect 263 ms 346668 KB Output isn't correct
6 Halted 0 ms 0 KB -