Submission #922434

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
922434	2024-02-05T13:57:56 Z	SNP011	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	477 ms	77116 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) {
	int mid = (R + L) >> 1;
	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]});
		if (mid - L >= 2) {
			dp[0][id] = max(dp[0][id], dp[3][2 * id] + dp[2][2 * id + 1]);
		}
		if (R - mid >= 2) {
			dp[0][id] = max(dp[0][id], dp[2][2 * id] + dp[4][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:51: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]
   51 |    if (discovery.size() >= L) {
      |        ~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	43100 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	43100 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	14 ms	43352 KB	Output is correct
2	Correct	13 ms	43100 KB	Output is correct
3	Correct	15 ms	43172 KB	Output is correct
4	Correct	24 ms	43356 KB	Output is correct
5	Correct	61 ms	44104 KB	Output is correct
6	Correct	13 ms	43100 KB	Output is correct
7	Correct	14 ms	43096 KB	Output is correct
8	Correct	15 ms	43096 KB	Output is correct
9	Correct	15 ms	43100 KB	Output is correct
10	Correct	26 ms	43352 KB	Output is correct
11	Correct	71 ms	44368 KB	Output is correct
12	Correct	16 ms	44380 KB	Output is correct
13	Correct	17 ms	44380 KB	Output is correct
14	Correct	19 ms	44380 KB	Output is correct
15	Correct	31 ms	44648 KB	Output is correct
16	Correct	88 ms	45652 KB	Output is correct
17	Correct	93 ms	72096 KB	Output is correct
18	Correct	100 ms	72212 KB	Output is correct
19	Correct	92 ms	72244 KB	Output is correct
20	Correct	130 ms	72556 KB	Output is correct
21	Correct	347 ms	73756 KB	Output is correct