Submission #69360

#	Time	Username	Problem	Language	Result	Execution time	Memory
69360		aome	Wild Boar (JOI18_wild_boar)	C++17	0 / 100	324 ms	277536 KiB

wild_boar

#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)

	Node merge(Node &x, Node &y, Node &z) {
		Node ret;
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				for (int k = 0; k < 4; ++k) {
					long long tmp = 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;
					for (int l = 0; l < 4; ++l) {
						if (ret.f[l].w > tmp) {
							for (int t = 3; t > l; --t) ret.f[t] = ret.f[t - 1];
							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;
							ret.f[l] = F(tmp, L, R);
							break;
						}
					}
				}
			}
		}
		return ret;
	}

	void modify(int i, int l, int r) {
		Node tmp;
		for (int i = 0; i < 4; ++i) {
			tmp.f[i] = f[arr[mid]][arr[mid + 1]][i];
		}
		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) {
	f[r][r][0].w = 0;
	priority_queue<Data> pq;
	for (auto i : G[r]) {
		int w = i.w, u = i.to, id = i.id;
		for (int j = 0; j < 4; ++j) {
			if (f[r][u][j].w > w) {
				for (int k = 3; k > j; --k) f[r][u][k] = f[r][u][k - 1];
				f[r][u][j] = F(0LL + w, id, id), pq.push({0LL + w, u, j}); break;
			}
		}
	}
	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;
				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, f[r][u][x].x, id); 
					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 <= 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
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38