Submission #922374

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
922374	2024-02-05T12:52:24 Z	SNP011	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	489 ms	60332 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 = 2e5 + 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] = 1ll * 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] = 1ll * discovery.size() - 1;
}

void updateDP(int id) {
	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]);
	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])});
}

struct segment {
	void init(int id, int L, int R) {
		if (L + 1 == R) {
			if (1ll * 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);
	}

	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);
	}
} 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;
		// cout << d << ", " << e << ": ";
		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]]);
		// cout << e - we[{edge[d]}] << "->" << st[u] << ", " << fn[u] << '\n';
		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:40:31: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   40 |    if (1ll * discovery.size() >= L) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	28760 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	9 ms	28760 KB	Output is correct
2	Correct	9 ms	29272 KB	Output is correct
3	Correct	9 ms	28700 KB	Output is correct
4	Correct	17 ms	28876 KB	Output is correct
5	Correct	49 ms	29224 KB	Output is correct
6	Correct	10 ms	28760 KB	Output is correct
7	Correct	9 ms	28764 KB	Output is correct
8	Correct	9 ms	28764 KB	Output is correct
9	Correct	10 ms	28936 KB	Output is correct
10	Correct	20 ms	29016 KB	Output is correct
11	Correct	61 ms	29172 KB	Output is correct
12	Correct	12 ms	30040 KB	Output is correct
13	Correct	12 ms	30044 KB	Output is correct
14	Correct	14 ms	30044 KB	Output is correct
15	Correct	26 ms	30092 KB	Output is correct
16	Correct	81 ms	30556 KB	Output is correct
17	Correct	84 ms	58084 KB	Output is correct
18	Correct	83 ms	58168 KB	Output is correct
19	Correct	91 ms	58280 KB	Output is correct
20	Correct	117 ms	58280 KB	Output is correct
21	Correct	309 ms	58796 KB	Output is correct