oj.uz

Submission #674484

# Submission time Handle Problem Language Result Execution time Memory
674484 2022-12-24T13:58:15 Z Sohsoh84 Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4662 ms 371744 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;
#define int			ll

const ll MAXN = 1e5 + 10;
const ll LOG = 40;
const ll INF = 1e18;

int n, q, t, cent_par[MAXN], H[MAXN], D[MAXN][LOG], sz[MAXN], 
    tin[MAXN][LOG], tout[MAXN][LOG], EV[MAXN], EU[MAXN];
ll w, lz[MAXN * LOG * 4], ans[MAXN], EW[MAXN];
pair<pll, pll> A[MAXN * LOG], sg[MAXN * LOG * 4];
vector<pll> adj[MAXN];
bool B[MAXN];

int dfs_sz(int v, int p) {
	sz[v] = 1;
	for (auto [u, w] : adj[v])
		if (!B[u] && u != p)
			sz[v] += dfs_sz(u, v);
	
	return sz[v];
}

int centroid(int v, int p, int tn) {
	for (auto [u, w] : adj[v])
		if (!B[u] && u != p && sz[u] * 2 > tn)
			return centroid(u, v, tn);

	return v;
}

void dfs(int v, int p, int lvl, ll d, int typ) {
	tin[v][lvl] = ++t;
	A[t] = {{d, typ}, {-INF, -1}};
	D[v][lvl] = D[p][lvl] + 1;

	for (auto [u, w] : adj[v])
		if (!B[u] && u != p)
			dfs(u, v, lvl, d + w, typ);

	tout[v][lvl] = t;
}

void build_tree(int v, int p, int lvl) {
	v = centroid(v, 0, dfs_sz(v, 0));

	cent_par[v] = p;
	H[v] = lvl;
	B[v] = true;

	tin[v][lvl] = ++t;
	D[v][lvl] = 0;
	A[t] = {{0, v}, {-INF, -1}};
	for (auto [u, w] : adj[v])
		if (!B[u])
			dfs(u, v, lvl, w, u);
	tout[v][lvl] = t;

	for (auto [u, w] : adj[v])
		if (!B[u])
			build_tree(u, v, lvl + 1);
}

inline void push(int v) {
	sg[v].X.X += lz[v];
	sg[v].Y.X += lz[v];
	if (v < (MAXN * LOG * 4))
		lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];

	lz[v] = 0;
}

inline void add(pair<pll, pll>& a, pll b) {
	if (b.X > a.X.X) {
		if (b.Y != a.X.Y) a.Y = a.X;
		a.X = b;
	} else if (b.X > a.Y.X && b.Y != a.X.Y) {
		a.Y = b;
	}
}

inline pair<pll, pll> merge(pair<pll, pll> a, pair<pll, pll> b) {
	add(a, b.X);
	add(a, b.Y);
	return a;
}

void build(int l = 1, int r = t, int v = 1) {
	if (l == r) sg[v] = A[l];
	else {
		int mid = (l + r) >> 1;
		build(l, mid, v << 1);
		build(mid + 1, r, v << 1 | 1);
		sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	}
}

void update(int ql, int qr, ll val, int l = 1, int r = t, int v = 1) {
	push(v);
	if (ql > r || qr < l) return;
	if (ql <= l && qr >= r) {
		lz[v] += val;
		push(v);
		return;
	}

	int mid = (l + r) >> 1;
	update(ql, qr, val, l, mid, v << 1);
	update(ql, qr, val, mid + 1, r, v << 1 | 1);
	sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}

pair<pll, pll> query(int ql, int qr, int l = 1, int r = t, int v = 1) {
	push(v);
	if (ql > r || qr < l) return {{-INF, -INF}, {-INF, -INF - 1}};
	if (ql <= l && qr >= r) return sg[v];
	
	int mid = (l + r) >> 1;
	return merge(query(ql, qr, l, mid, v << 1),
			 query(ql, qr, mid + 1, r, v << 1 | 1));
}

set<pll> ans_st;

void update_ans(int v) {
	ans_st.erase({ans[v], v});
	auto e = query(tin[v][H[v]], tout[v][H[v]]);
	ans[v] = max(max(0ll, e.X.X), e.X.X + e.Y.X);
	ans_st.insert({ans[v], v});
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q >> w;
	for (int i = 0; i < n - 1; i++) {
		cin >> EV[i] >> EU[i] >> EW[i];
		adj[EU[i]].push_back({EV[i], EW[i]});
		adj[EV[i]].push_back({EU[i], EW[i]});
	}

	build_tree(1, 0, 0);
	build();
	for (int v = 1; v <= n; v++) update_ans(v);

	ll last = 0;
	while (q--) {
		ll td, tw, ind, delta, rw, u, v;
		cin >> td >> tw;
		
		ind = (td + last) % (n - 1), rw = (tw + last) % w;
		u = EU[ind], v = EV[ind];
		delta = (rw - EW[ind]);
		EW[ind] = rw;

		if (H[u] > H[v]) swap(u, v);
	
		int c = u;
		while (c) {
			int au = u, av = v, lvl = H[c];
			if (D[au][lvl] > D[av][lvl]) swap(au, av);

			update(tin[av][lvl], tout[av][lvl], delta);
			update_ans(c);
			c = cent_par[c];
		}

		last = ans_st.rbegin() -> X;
		cout << last << endl;
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 2 ms 2900 KB Output is correct
16 Correct 2 ms 2900 KB Output is correct
17 Correct 2 ms 2900 KB Output is correct
18 Correct 3 ms 2976 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 2 ms 2900 KB Output is correct
16 Correct 2 ms 2900 KB Output is correct
17 Correct 2 ms 2900 KB Output is correct
18 Correct 3 ms 2976 KB Output is correct
19 Correct 24 ms 4828 KB Output is correct
20 Correct 28 ms 4820 KB Output is correct
21 Correct 33 ms 4900 KB Output is correct
22 Correct 39 ms 5732 KB Output is correct
23 Correct 46 ms 15512 KB Output is correct
24 Correct 61 ms 15828 KB Output is correct
25 Correct 70 ms 16072 KB Output is correct
26 Correct 88 ms 16524 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 10 ms 2772 KB Output is correct
5 Correct 42 ms 3080 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 13 ms 3540 KB Output is correct
11 Correct 57 ms 3856 KB Output is correct
12 Correct 8 ms 9940 KB Output is correct
13 Correct 8 ms 10076 KB Output is correct
14 Correct 10 ms 10196 KB Output is correct
15 Correct 24 ms 10196 KB Output is correct
16 Correct 88 ms 10528 KB Output is correct
17 Correct 148 ms 140216 KB Output is correct
18 Correct 149 ms 141456 KB Output is correct
19 Correct 156 ms 143620 KB Output is correct
20 Correct 177 ms 144048 KB Output is correct
21 Correct 299 ms 144656 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4820 KB Output is correct
2 Correct 48 ms 4932 KB Output is correct
3 Correct 216 ms 5144 KB Output is correct
4 Correct 416 ms 5508 KB Output is correct
5 Correct 38 ms 29732 KB Output is correct
6 Correct 117 ms 29792 KB Output is correct
7 Correct 427 ms 30016 KB Output is correct
8 Correct 838 ms 30316 KB Output is correct
9 Correct 166 ms 173760 KB Output is correct
10 Correct 309 ms 178300 KB Output is correct
11 Correct 805 ms 178892 KB Output is correct
12 Correct 1474 ms 179060 KB Output is correct
13 Correct 313 ms 343256 KB Output is correct
14 Correct 482 ms 358072 KB Output is correct
15 Correct 1276 ms 359536 KB Output is correct
16 Correct 1962 ms 360396 KB Output is correct
17 Correct 3509 ms 360264 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2989 ms 347916 KB Output is correct
2 Correct 2874 ms 351584 KB Output is correct
3 Correct 2824 ms 351216 KB Output is correct
4 Correct 2895 ms 351292 KB Output is correct
5 Correct 3041 ms 281380 KB Output is correct
6 Correct 2735 ms 236728 KB Output is correct
7 Correct 3978 ms 364072 KB Output is correct
8 Correct 3921 ms 364104 KB Output is correct
9 Correct 3890 ms 364092 KB Output is correct
10 Correct 3933 ms 363820 KB Output is correct
11 Correct 4067 ms 359192 KB Output is correct
12 Correct 3566 ms 244392 KB Output is correct
13 Correct 4294 ms 371524 KB Output is correct
14 Correct 4285 ms 371744 KB Output is correct
15 Correct 4248 ms 371492 KB Output is correct
16 Correct 4662 ms 371188 KB Output is correct
17 Correct 4271 ms 365868 KB Output is correct
18 Correct 3964 ms 247524 KB Output is correct
19 Correct 4280 ms 371576 KB Output is correct
20 Correct 4272 ms 371440 KB Output is correct
21 Correct 4351 ms 371616 KB Output is correct
22 Correct 4415 ms 371104 KB Output is correct
23 Correct 4264 ms 365868 KB Output is correct
24 Correct 3574 ms 247264 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 2 ms 2900 KB Output is correct
16 Correct 2 ms 2900 KB Output is correct
17 Correct 2 ms 2900 KB Output is correct
18 Correct 3 ms 2976 KB Output is correct
19 Correct 24 ms 4828 KB Output is correct
20 Correct 28 ms 4820 KB Output is correct
21 Correct 33 ms 4900 KB Output is correct
22 Correct 39 ms 5732 KB Output is correct
23 Correct 46 ms 15512 KB Output is correct
24 Correct 61 ms 15828 KB Output is correct
25 Correct 70 ms 16072 KB Output is correct
26 Correct 88 ms 16524 KB Output is correct
27 Correct 1 ms 2772 KB Output is correct
28 Correct 2 ms 2772 KB Output is correct
29 Correct 2 ms 2772 KB Output is correct
30 Correct 10 ms 2772 KB Output is correct
31 Correct 42 ms 3080 KB Output is correct
32 Correct 1 ms 2644 KB Output is correct
33 Correct 2 ms 3412 KB Output is correct
34 Correct 3 ms 3412 KB Output is correct
35 Correct 3 ms 3412 KB Output is correct
36 Correct 13 ms 3540 KB Output is correct
37 Correct 57 ms 3856 KB Output is correct
38 Correct 8 ms 9940 KB Output is correct
39 Correct 8 ms 10076 KB Output is correct
40 Correct 10 ms 10196 KB Output is correct
41 Correct 24 ms 10196 KB Output is correct
42 Correct 88 ms 10528 KB Output is correct
43 Correct 148 ms 140216 KB Output is correct
44 Correct 149 ms 141456 KB Output is correct
45 Correct 156 ms 143620 KB Output is correct
46 Correct 177 ms 144048 KB Output is correct
47 Correct 299 ms 144656 KB Output is correct
48 Correct 7 ms 4820 KB Output is correct
49 Correct 48 ms 4932 KB Output is correct
50 Correct 216 ms 5144 KB Output is correct
51 Correct 416 ms 5508 KB Output is correct
52 Correct 38 ms 29732 KB Output is correct
53 Correct 117 ms 29792 KB Output is correct
54 Correct 427 ms 30016 KB Output is correct
55 Correct 838 ms 30316 KB Output is correct
56 Correct 166 ms 173760 KB Output is correct
57 Correct 309 ms 178300 KB Output is correct
58 Correct 805 ms 178892 KB Output is correct
59 Correct 1474 ms 179060 KB Output is correct
60 Correct 313 ms 343256 KB Output is correct
61 Correct 482 ms 358072 KB Output is correct
62 Correct 1276 ms 359536 KB Output is correct
63 Correct 1962 ms 360396 KB Output is correct
64 Correct 3509 ms 360264 KB Output is correct
65 Correct 2989 ms 347916 KB Output is correct
66 Correct 2874 ms 351584 KB Output is correct
67 Correct 2824 ms 351216 KB Output is correct
68 Correct 2895 ms 351292 KB Output is correct
69 Correct 3041 ms 281380 KB Output is correct
70 Correct 2735 ms 236728 KB Output is correct
71 Correct 3978 ms 364072 KB Output is correct
72 Correct 3921 ms 364104 KB Output is correct
73 Correct 3890 ms 364092 KB Output is correct
74 Correct 3933 ms 363820 KB Output is correct
75 Correct 4067 ms 359192 KB Output is correct
76 Correct 3566 ms 244392 KB Output is correct
77 Correct 4294 ms 371524 KB Output is correct
78 Correct 4285 ms 371744 KB Output is correct
79 Correct 4248 ms 371492 KB Output is correct
80 Correct 4662 ms 371188 KB Output is correct
81 Correct 4271 ms 365868 KB Output is correct
82 Correct 3964 ms 247524 KB Output is correct
83 Correct 4280 ms 371576 KB Output is correct
84 Correct 4272 ms 371440 KB Output is correct
85 Correct 4351 ms 371616 KB Output is correct
86 Correct 4415 ms 371104 KB Output is correct
87 Correct 4264 ms 365868 KB Output is correct
88 Correct 3574 ms 247264 KB Output is correct
89 Correct 3035 ms 350148 KB Output is correct
90 Correct 3216 ms 354660 KB Output is correct
91 Correct 3586 ms 361164 KB Output is correct
92 Correct 3776 ms 363216 KB Output is correct
93 Correct 4116 ms 366148 KB Output is correct
94 Correct 4174 ms 367320 KB Output is correct
95 Correct 4428 ms 369020 KB Output is correct
96 Correct 4202 ms 368440 KB Output is correct
97 Correct 4245 ms 369080 KB Output is correct
98 Correct 4212 ms 370976 KB Output is correct
99 Correct 4277 ms 368660 KB Output is correct
100 Correct 4196 ms 368608 KB Output is correct