Submission #926072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
926072	2024-02-12T14:20:50 Z	SNP011	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	427 ms	62008 KB

diameter

#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define pii pair<long long, long long>
#define int long long
const int maxn = 2e5 + 5, inf = 1e18;
 
int lastans;
int n, q, w;
vector<pii> adj[maxn], edge;
map<pii, int> va;
vector<int> dis;
bool vis[maxn];
int dp[4 * maxn][5], st[maxn], fn[maxn];
int h[maxn], lazy[4 * maxn], _h[maxn];
 
void dfs(int v) {
	vis[v] = 1;
	st[v] = dis.size();
	dis.pb(h[v]);
	for (auto[w, u]: adj[v]) {
		if (!vis[u]) {
			_h[u] = _h[v] + 1;
			h[u] = h[v] + w;
			dfs(u);
			dis.pb(h[v]);
		}
	}
	fn[v] = dis.size() - 1;
}
 
void updateDP(int id, int L, int R) {
	int mid = (R + L >> 1);
	int lc = 2 * id, rc = 2 * id + 1;
	if (R - L >= 3) {
		dp[id][0] = 0 - inf;
		if (mid - L >= 3) {
			dp[id][0] = max(dp[id][0], dp[lc][0]);
		}
		if (R - mid >= 3) {
			dp[id][0] = max(dp[id][0], dp[rc][0]);
		}
		if (mid - L >= 2) {
			dp[id][0] = max(dp[id][0], dp[lc][3] + dp[rc][2]);
		}
		if (R - mid >= 2) {
			dp[id][0] = max(dp[id][0], dp[lc][2] + dp[rc][4]);
		}
	}
	dp[id][1] = min(dp[lc][1], dp[rc][1]);
	dp[id][2] = max(dp[lc][2], dp[rc][2]);
	if (R - L >= 2) {
		dp[id][3] = max({dp[lc][3], dp[rc][3], dp[lc][2] - (2 * dp[rc][1])});
		dp[id][4] = max({dp[lc][4], dp[rc][4], dp[rc][2] - (2 * dp[lc][1])});
	}
}
 
void printDP(int id, int L, int R) {
	cout << L << ", " << R - 1 << ": \n";
	cout << "dp[0] = " << dp[id][0] << '\n';
	cout << "dp[1] = " << dp[id][1] << '\n';
	cout << "dp[2] = " << dp[id][2] << '\n';
	cout << "dp[3] = " << dp[id][3] << '\n';
	cout << "dp[4] = " << dp[id][4] << '\n';
	cout << "\n\n-----------------\n\n";
}
 
struct segment {
	void spread(int id, int L, int R) {
		int mid = (R + L) >> 1;

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

		dp[2 * id + 1][1] += lazy[id];
		dp[2 * id + 1][2] += lazy[id];

		if (R - mid >= 2) {
			dp[2 * id + 1][3] -= lazy[id];
			dp[2 * id + 1][4] -= lazy[id];	
		}
 
		lazy[2 * id] += lazy[id];
		lazy[2 * id + 1] += lazy[id];
		lazy[id] = 0;
	}
 
	void init(int id, int L, int R) {
		if (L + 1 == R) {
			dp[id][1] = dis[L];
			dp[id][2] = dis[L];
			// printDP(id, L, R);
			return;
		}
		int mid = (R + L) >> 1;
		init(2 * id, L, mid);
		init(2 * id + 1, mid, R);
		updateDP(id, L, R);
		// printDP(id, L, R);
	}
 
	void update(int id, int L, int R, int l, int r, int val) {
		if (L == l and R == r) {
			dp[id][1] += val;
			dp[id][2] += val;
			dp[id][3] -= val;
			dp[id][4] -= 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);
		// printDP(id, L, R);
	}
} seg;
 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  	// freopen("inp.txt", "r", stdin);
 	// freopen("wrong.txt", "w", stdout);
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j < 5; j++) {
			dp[i][j] = (j == 1 ? inf : 0 - inf);
		}
	}
 
	cin >> n >> q >> w;
	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});
		va[{u, v}] = _w;
		va[{v, u}] = _w;
		edge.pb({u, v});
	}
	dis.pb(-1);
	dfs(1);
	seg.init(1, 1, 2 * n);
	while (q--) {
		int i, x;
		cin >> i >> x;
		i = (i + lastans) % (n - 1);
		x = (x + lastans) % w;
		int u = edge[i].first, v = edge[i].second;
 
		if (_h[u] < _h[v]) {
			swap(u, v);
		} // h[u] > h[v]
		seg.update(1, 1, 2 * n, st[u], fn[u] + 1, x - va[{u, v}]);
		cout << max(dp[1][0], dp[1][2]) << '\n';
		lastans = max(dp[1][0], dp[1][2]);
		va[{u, v}] = x;
		va[{v, u}] = x;
	}
	return 0;
}

Compilation message

diameter.cpp: In function 'void updateDP(long long int, long long int, long long int)':
diameter.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int mid = (R + L >> 1);
      |             ~~^~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	18008 KB	Output is correct
2	Correct	4 ms	18008 KB	Output is correct
3	Correct	4 ms	18232 KB	Output is correct
4	Correct	10 ms	18268 KB	Output is correct
5	Correct	34 ms	19024 KB	Output is correct
6	Correct	4 ms	18008 KB	Output is correct
7	Correct	4 ms	18268 KB	Output is correct
8	Correct	4 ms	18268 KB	Output is correct
9	Correct	5 ms	18520 KB	Output is correct
10	Correct	13 ms	18524 KB	Output is correct
11	Correct	52 ms	19616 KB	Output is correct
12	Correct	6 ms	19548 KB	Output is correct
13	Correct	7 ms	19660 KB	Output is correct
14	Correct	8 ms	19804 KB	Output is correct
15	Correct	20 ms	20056 KB	Output is correct
16	Correct	75 ms	20836 KB	Output is correct
17	Correct	92 ms	60488 KB	Output is correct
18	Correct	81 ms	59860 KB	Output is correct
19	Correct	85 ms	59948 KB	Output is correct
20	Incorrect	120 ms	59980 KB	Output isn't correct
21	Halted	0 ms	0 KB	-