Submission #922402

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
922402	2024-02-05T13:24:02 Z	SNP011	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	509 ms	75532 KB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define pb push_back
const int maxn = 4e5 + 5;

int h[maxn], dp[5][4 * maxn], lastans;
int lazy[4 * maxn], st[maxn], fn[maxn];
vector<pii> adj[maxn];
vector<int> discovery;
map<pii, int> we;

void dfs(int v, int par = 0) {
	st[v] = discovery.size();
	discovery.pb(h[v]);
	for (auto[w, u]: adj[v]) {
		if (u != par) {
			h[u] = h[v] + w;
			dfs(u, v);
			discovery.pb(h[v]);
		}
	}
	fn[v] = discovery.size() - 1;
}

void updateDP(int id, int L, int R) {
	if (R - L >= 2) {
		dp[3][id] = max({dp[3][2 * id], dp[3][2 * id + 1], dp[2][2 * id] - (2 * dp[1][2 * id + 1])});
		dp[4][id] = max({dp[4][2 * id], dp[4][2 * id + 1], dp[2][2 * id + 1] - (2 * dp[1][2 * id])});
	}
	if (R - L >= 3) {
		dp[0][id] = max({dp[0][2 * id], dp[0][2 * id + 1], dp[2][2 * id] + dp[4][2 * id + 1], dp[3][2 * id] + dp[2][2 * id + 1]});
	}
	dp[1][id] = min(dp[1][2 * id], dp[1][2 * id + 1]);
	dp[2][id] = max(dp[2][2 * id], dp[2][2 * id + 1]);
}

struct segment {
	void init(int id, int L, int R) {
		if (L + 1 == R) {
			if (discovery.size() >= L) {
				dp[1][id] = discovery[L];
				dp[2][id] = discovery[L];
			}
			return;
		}
		int mid = (R + L) >> 1;
		init(2 * id, L, mid);
		init(2 * id + 1, mid, R);
		updateDP(id, L, R);
	}

	void spread(int id, int L, int R) {
		int mid = (R + L) >> 1;

		dp[1][2 * id] += lazy[id];
		dp[2][2 * id] += lazy[id];
		if (mid - L >= 2) {
			dp[3][2 * id] -= lazy[id];
			dp[4][2 * id] -= lazy[id];
		}

		dp[1][2 * id + 1] += lazy[id];
		dp[2][2 * id + 1] += lazy[id];
		if (R - mid >= 2) {
			dp[3][2 * id + 1] -= lazy[id];
			dp[4][2 * id + 1] -= lazy[id];
		}

		lazy[2 * id] += lazy[id];
		lazy[2 * id + 1] += lazy[id];
		lazy[id] = 0;
	}

	void update(int id, int L, int R, int l, int r, int val) {
		if (L == l and R == r) {
			dp[1][id] += val;
			dp[2][id] += val;
			if (R - L >= 2) {
				dp[3][id] -= val;
				dp[4][id] -= val;	
			}
			lazy[id] += val;
			return;
		}
		spread(id, L, R);
		int mid = (R + L) >> 1;
		if (l < mid) {
			update(2 * id, L, mid, l, min(r, mid), val);
		}
		if (r > mid) {
			update(2 * id + 1, mid, R, max(l, mid), r, val);
		}
		updateDP(id, L, R);
	}
} seg;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q, w;
	cin >> n >> q >> w;
	vector<pii> edge;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[v].pb({w, u});
		adj[u].pb({w, v});
		we[{u, v}] = w;
		we[{v, u}] = w;
		edge.pb({u, v});
	}
	discovery.pb(-1);
	dfs(1);
	seg.init(1, 1, maxn);
	while (q--) {
		int d, e;
		cin >> d >> e;
		d = (d + lastans) % (n - 1);
		e = (e + lastans) % w;
		int u = edge[d].first, v = edge[d].second;
		if (h[u] < h[v]) {
			swap(u, v);
		} // h[u] >= h[v]
		seg.update(1, 1, maxn, st[u], fn[u] + 1, e - we[edge[d]]);
		we[{u, v}] = e;
		we[{v, u}] = e;
		lastans = dp[0][1];
		cout << dp[0][1] << '\n';
	}
	return 0;
}

Compilation message

diameter.cpp: In member function 'void segment::init(long long int, long long int, long long int)':
diameter.cpp:44:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |    if (discovery.size() >= L) {
      |        ~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	43096 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	43096 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	43096 KB	Output is correct
2	Correct	15 ms	43152 KB	Output is correct
3	Correct	13 ms	43100 KB	Output is correct
4	Correct	23 ms	43348 KB	Output is correct
5	Correct	66 ms	44112 KB	Output is correct
6	Correct	12 ms	43128 KB	Output is correct
7	Correct	13 ms	43348 KB	Output is correct
8	Correct	13 ms	43100 KB	Output is correct
9	Correct	14 ms	43096 KB	Output is correct
10	Correct	27 ms	43456 KB	Output is correct
11	Correct	68 ms	44480 KB	Output is correct
12	Correct	16 ms	44380 KB	Output is correct
13	Correct	16 ms	44380 KB	Output is correct
14	Correct	18 ms	44240 KB	Output is correct
15	Correct	31 ms	44632 KB	Output is correct
16	Correct	86 ms	45632 KB	Output is correct
17	Correct	90 ms	71344 KB	Output is correct
18	Correct	94 ms	71904 KB	Output is correct
19	Correct	96 ms	71852 KB	Output is correct
20	Correct	123 ms	71996 KB	Output is correct
21	Correct	333 ms	73012 KB	Output is correct