oj.uz

Submission #69362

# Submission time Handle Problem Language Result Execution time Memory
69362 2018-08-20T16:03:05 Z aome Wild Boar (JOI18_wild_boar) C++17
0 / 100
 272 ms 277536 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) {}

	void dbg() { cout << "#F " << w << ' ' << x << ' ' << y << '\n';}
};

int n, m, l, q;
int arr[L];
F f[N][N][4];
vector<Edge> G[N];

struct SegmentTree {
	struct Node { F f[4]; };

	Node T[L << 2];

	#define mid ((l + r) >> 1)

	struct Data {
		long long w; int i, j, k;

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

	Node merge(Node &x, Node &y, Node &z) {
		Node ret;
		vector<Data> 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 = x.f[i].w + y.f[j].w + z.f[k].w;
					if (x.f[i].y == z.f[k].x || z.f[k].y == y.f[j].x) continue;
					vec.push_back({w, i, j, k});
				}
			}
		}
		sort(vec.begin(), vec.end());
		for (auto v : vec) {
			long long w = v.w;
			int i = v.i, j = v.j, k = v.k;
			int L = x.f[i].x; if (L == 0) L = z.f[k].x;
			int R = y.f[j].y; if (R == 0) R = z.f[k].y;
			bool flag = 0;
			for (int l = 0; l < 4; ++l) {
				flag |= (L == ret.f[l].x && R == ret.f[l].y);
			}
			if (flag) continue;
			for (int l = 0; l < 4; ++l) {
				if (ret.f[l].w > w) {
					for (int t = 3; t > l; --t) ret.f[t] = ret.f[t - 1];
					ret.f[l] = F(w, L, R); break;
				}
			}
		}
		return ret;
	}

	void modify(int i, int l, int r) {
		Node tmp;
		for (int j = 0; j < 4; ++j) {
			tmp.f[j] = f[arr[mid]][arr[mid + 1]][j];
		}
		T[i] = merge(T[i << 1], T[i << 1 | 1], tmp);
	}

	void build(int i, int l, int r) {
		if (l == r) { T[i].f[0].w = 0; return; }
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		modify(i, l, r);
	}

	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);
		modify(i, l, r);
	}

	#undef mid
} IT;

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

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

void cal(int r) {
	priority_queue<Data> pq;
	f[r][r][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 (f[r][u][x].w != w) continue;
		for (auto i : G[u]) {
			int w = i.w, v = i.to, id = i.id;
			for (int j = 0; j < 4; ++j) {
				if (f[r][u][x].y == id) continue;
				int L = f[r][u][x].x, R = id;
				if (L == 0) L = id;
				bool flag = 0;
				for (int k = 0; k < 4; ++k) {
					flag |= (L == f[r][v][k].x && R == f[r][v][k].y);
				}
				if (flag) continue;
				if (f[r][v][j].w > f[r][u][x].w + w) {
					for (int k = 3; k > j; --k) f[r][v][k] = f[r][v][k - 1];
					f[r][v][j] = F(f[r][u][x].w + w, L, R);
					pq.push({f[r][v][j].w, v, j}); break;
				}
			}
		}
	}
}

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) {
	// 			f[i][j][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].f[0].w;
		cout << (res == INF ? -1 : res) << '\n';
	}
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 277240 KB Output is correct
2 Correct 226 ms 277252 KB Output is correct
3 Correct 241 ms 277432 KB Output is correct
4 Correct 260 ms 277432 KB Output is correct
5 Incorrect 240 ms 277536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 277240 KB Output is correct
2 Correct 226 ms 277252 KB Output is correct
3 Correct 241 ms 277432 KB Output is correct
4 Correct 260 ms 277432 KB Output is correct
5 Incorrect 240 ms 277536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 277240 KB Output is correct
2 Correct 226 ms 277252 KB Output is correct
3 Correct 241 ms 277432 KB Output is correct
4 Correct 260 ms 277432 KB Output is correct
5 Incorrect 240 ms 277536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 277240 KB Output is correct
2 Correct 226 ms 277252 KB Output is correct
3 Correct 241 ms 277432 KB Output is correct
4 Correct 260 ms 277432 KB Output is correct
5 Incorrect 240 ms 277536 KB Output isn't correct
6 Halted 0 ms 0 KB -