oj.uz

Submission #926050

# Submission time Handle Problem Language Result Execution time Memory
926050 2024-02-12T13:47:24 Z SNP011 Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 196 ms 115352 KB 
#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[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 lc = 2 * id, rc = 2 * id + 1;
	dp[id][0] = max({dp[lc][0], dp[rc][0], dp[lc][2] + dp[rc][4], dp[lc][3] + dp[rc][2]});
	dp[id][1] = min(dp[lc][1], dp[rc][1]);
	dp[id][2] = max(dp[lc][2], dp[rc][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) {
		dp[2 * id][1] += lazy[id];
		dp[2 * id][2] += lazy[id];
		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];
		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);
		// 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);
		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);
		// 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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19544 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 3 ms 19548 KB Output is correct
4 Correct 4 ms 19688 KB Output is correct
5 Correct 4 ms 19548 KB Output is correct
6 Correct 4 ms 19544 KB Output is correct
7 Correct 4 ms 19548 KB Output is correct
8 Correct 4 ms 19544 KB Output is correct
9 Correct 4 ms 19548 KB Output is correct
10 Correct 4 ms 19708 KB Output is correct
11 Correct 4 ms 19544 KB Output is correct
12 Correct 4 ms 19688 KB Output is correct
13 Correct 4 ms 19548 KB Output is correct
14 Correct 3 ms 19548 KB Output is correct
15 Correct 4 ms 19548 KB Output is correct
16 Correct 4 ms 19684 KB Output is correct
17 Correct 4 ms 19548 KB Output is correct
18 Correct 4 ms 19548 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19544 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 3 ms 19548 KB Output is correct
4 Correct 4 ms 19688 KB Output is correct
5 Correct 4 ms 19548 KB Output is correct
6 Correct 4 ms 19544 KB Output is correct
7 Correct 4 ms 19548 KB Output is correct
8 Correct 4 ms 19544 KB Output is correct
9 Correct 4 ms 19548 KB Output is correct
10 Correct 4 ms 19708 KB Output is correct
11 Correct 4 ms 19544 KB Output is correct
12 Correct 4 ms 19688 KB Output is correct
13 Correct 4 ms 19548 KB Output is correct
14 Correct 3 ms 19548 KB Output is correct
15 Correct 4 ms 19548 KB Output is correct
16 Correct 4 ms 19684 KB Output is correct
17 Correct 4 ms 19548 KB Output is correct
18 Correct 4 ms 19548 KB Output is correct
19 Correct 7 ms 20060 KB Output is correct
20 Correct 7 ms 20056 KB Output is correct
21 Correct 8 ms 20060 KB Output is correct
22 Correct 8 ms 20060 KB Output is correct
23 Correct 12 ms 21340 KB Output is correct
24 Correct 12 ms 21240 KB Output is correct
25 Correct 12 ms 21440 KB Output is correct
26 Correct 13 ms 21592 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19548 KB Output is correct
2 Correct 4 ms 19548 KB Output is correct
3 Correct 4 ms 19700 KB Output is correct
4 Correct 9 ms 19928 KB Output is correct
5 Correct 30 ms 20604 KB Output is correct
6 Correct 3 ms 19548 KB Output is correct
7 Correct 4 ms 19804 KB Output is correct
8 Correct 5 ms 19804 KB Output is correct
9 Correct 5 ms 19804 KB Output is correct
10 Correct 12 ms 19960 KB Output is correct
11 Correct 47 ms 21076 KB Output is correct
12 Correct 7 ms 21084 KB Output is correct
13 Correct 7 ms 21084 KB Output is correct
14 Correct 8 ms 21084 KB Output is correct
15 Correct 19 ms 21524 KB Output is correct
16 Correct 67 ms 22448 KB Output is correct
17 Incorrect 81 ms 56240 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19804 KB Output is correct
2 Correct 10 ms 20060 KB Output is correct
3 Correct 31 ms 20516 KB Output is correct
4 Correct 62 ms 21440 KB Output is correct
5 Correct 11 ms 22680 KB Output is correct
6 Correct 17 ms 22916 KB Output is correct
7 Correct 46 ms 23376 KB Output is correct
8 Correct 82 ms 23796 KB Output is correct
9 Correct 38 ms 36684 KB Output is correct
10 Incorrect 50 ms 36780 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 115352 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19544 KB Output is correct
2 Correct 4 ms 19544 KB Output is correct
3 Correct 3 ms 19548 KB Output is correct
4 Correct 4 ms 19688 KB Output is correct
5 Correct 4 ms 19548 KB Output is correct
6 Correct 4 ms 19544 KB Output is correct
7 Correct 4 ms 19548 KB Output is correct
8 Correct 4 ms 19544 KB Output is correct
9 Correct 4 ms 19548 KB Output is correct
10 Correct 4 ms 19708 KB Output is correct
11 Correct 4 ms 19544 KB Output is correct
12 Correct 4 ms 19688 KB Output is correct
13 Correct 4 ms 19548 KB Output is correct
14 Correct 3 ms 19548 KB Output is correct
15 Correct 4 ms 19548 KB Output is correct
16 Correct 4 ms 19684 KB Output is correct
17 Correct 4 ms 19548 KB Output is correct
18 Correct 4 ms 19548 KB Output is correct
19 Correct 7 ms 20060 KB Output is correct
20 Correct 7 ms 20056 KB Output is correct
21 Correct 8 ms 20060 KB Output is correct
22 Correct 8 ms 20060 KB Output is correct
23 Correct 12 ms 21340 KB Output is correct
24 Correct 12 ms 21240 KB Output is correct
25 Correct 12 ms 21440 KB Output is correct
26 Correct 13 ms 21592 KB Output is correct
27 Correct 3 ms 19548 KB Output is correct
28 Correct 4 ms 19548 KB Output is correct
29 Correct 4 ms 19700 KB Output is correct
30 Correct 9 ms 19928 KB Output is correct
31 Correct 30 ms 20604 KB Output is correct
32 Correct 3 ms 19548 KB Output is correct
33 Correct 4 ms 19804 KB Output is correct
34 Correct 5 ms 19804 KB Output is correct
35 Correct 5 ms 19804 KB Output is correct
36 Correct 12 ms 19960 KB Output is correct
37 Correct 47 ms 21076 KB Output is correct
38 Correct 7 ms 21084 KB Output is correct
39 Correct 7 ms 21084 KB Output is correct
40 Correct 8 ms 21084 KB Output is correct
41 Correct 19 ms 21524 KB Output is correct
42 Correct 67 ms 22448 KB Output is correct
43 Incorrect 81 ms 56240 KB Output isn't correct
44 Halted 0 ms 0 KB -