Submission #69495

#	Time	Username	Problem	Language	Result	Execution time	Memory
69495		aome	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	13279 ms	388356 KiB

wild_boar

#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];
long long f[N][N];
bool vis[N][N];
bool memo[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;
		if (cnt1[vec[i].x] == 2 || cnt2[vec[i].y] == 2 || sz == M) continue;
		vis[vec[i].x][vec[i].y] = 1;
		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;
		vector< pair<int, int> > vec2;
		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;
					f[L][R] = min(f[L][R], w);
					if (!memo[L][R]) {
						memo[L][R] = 1, vec2.push_back({L, R});
					}
				}
			}
		}
		for (auto i : vec2) {
			int L = i.first, R = i.second;
			vec.push_back({f[L][R], L, R});
			f[L][R] = INF, memo[L][R] = 0;
		}
		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();

		bool found = 0;
		for (int i = 0; i < M; ++i) {
			found |= d[r][u].a[i].w == W && d[r][u].a[i].x == x && d[r][u].a[i].y == y;
		}
		if (!found) continue;

		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];
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= m; ++j) f[i][j] = INF;
	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 (stderr)

wild_boar.cpp: In function 'int add(std::vector<F>&, Data&, int)':
wild_boar.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); ++i) {
                  ~~^~~~~~~~~~~~
wild_boar.cpp:54:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (i == pos) ret = sz; cur.a[sz++] = vec[i];
   ^~
wild_boar.cpp:54: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 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38