oj.uz

답안 #926083

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926083 2024-02-12T14:35:29 Z SNP011 Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 592 ms 74052 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[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 and R - mid >= 1) {
			dp[id][0] = max(dp[id][0], dp[lc][3] + dp[rc][2]);
		}
		if (R - mid >= 2 and mid - L >= 1) {
			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] = 0 - inf;
		dp[id][4] = 0 - inf;
		if (mid - L >= 2) {
			dp[id][3] = max(dp[id][3], dp[lc][3]);
			dp[id][4] = max(dp[id][4], dp[lc][4]);
		}
		if (R - mid >= 2) {
			dp[id][3] = max(dp[id][3], dp[rc][3]);
			dp[id][4] = max(dp[id][4], dp[rc][4]);
		}
		if (mid - L >= 1 and R - mid >= 1) {
			dp[id][3] = max({dp[id][3], dp[lc][2] - (2 * dp[rc][1])});
			dp[id][4] = max({dp[id][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 (mid - L >= 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;
			if (R - L >= 2) {
				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
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 18008 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 4 ms 18008 KB Output is correct
5 Correct 3 ms 18008 KB Output is correct
6 Correct 4 ms 18008 KB Output is correct
7 Correct 4 ms 18008 KB Output is correct
8 Correct 4 ms 18012 KB Output is correct
9 Correct 4 ms 18012 KB Output is correct
10 Correct 4 ms 18268 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 4 ms 18012 KB Output is correct
13 Correct 4 ms 18268 KB Output is correct
14 Correct 3 ms 18268 KB Output is correct
15 Correct 4 ms 18268 KB Output is correct
16 Correct 3 ms 18268 KB Output is correct
17 Correct 3 ms 18268 KB Output is correct
18 Correct 3 ms 18268 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 18008 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 4 ms 18008 KB Output is correct
5 Correct 3 ms 18008 KB Output is correct
6 Correct 4 ms 18008 KB Output is correct
7 Correct 4 ms 18008 KB Output is correct
8 Correct 4 ms 18012 KB Output is correct
9 Correct 4 ms 18012 KB Output is correct
10 Correct 4 ms 18268 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 4 ms 18012 KB Output is correct
13 Correct 4 ms 18268 KB Output is correct
14 Correct 3 ms 18268 KB Output is correct
15 Correct 4 ms 18268 KB Output is correct
16 Correct 3 ms 18268 KB Output is correct
17 Correct 3 ms 18268 KB Output is correct
18 Correct 3 ms 18268 KB Output is correct
19 Correct 8 ms 18520 KB Output is correct
20 Correct 8 ms 18524 KB Output is correct
21 Correct 8 ms 18524 KB Output is correct
22 Correct 9 ms 18520 KB Output is correct
23 Correct 15 ms 19804 KB Output is correct
24 Correct 13 ms 19804 KB Output is correct
25 Correct 13 ms 19696 KB Output is correct
26 Correct 13 ms 20060 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Correct 4 ms 18008 KB Output is correct
3 Correct 4 ms 18268 KB Output is correct
4 Correct 11 ms 18340 KB Output is correct
5 Correct 42 ms 18440 KB Output is correct
6 Correct 3 ms 18012 KB Output is correct
7 Correct 4 ms 18264 KB Output is correct
8 Correct 4 ms 18224 KB Output is correct
9 Correct 5 ms 18264 KB Output is correct
10 Correct 16 ms 18248 KB Output is correct
11 Correct 60 ms 18780 KB Output is correct
12 Correct 6 ms 19548 KB Output is correct
13 Correct 7 ms 19548 KB Output is correct
14 Correct 8 ms 19548 KB Output is correct
15 Correct 21 ms 19804 KB Output is correct
16 Correct 77 ms 20052 KB Output is correct
17 Correct 83 ms 59932 KB Output is correct
18 Correct 83 ms 59848 KB Output is correct
19 Correct 84 ms 59968 KB Output is correct
20 Correct 108 ms 60080 KB Output is correct
21 Correct 270 ms 60476 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18520 KB Output is correct
2 Correct 11 ms 18524 KB Output is correct
3 Correct 37 ms 18788 KB Output is correct
4 Correct 73 ms 19028 KB Output is correct
5 Correct 10 ms 21080 KB Output is correct
6 Correct 18 ms 21244 KB Output is correct
7 Correct 55 ms 21336 KB Output is correct
8 Correct 107 ms 21796 KB Output is correct
9 Correct 47 ms 37716 KB Output is correct
10 Correct 61 ms 37612 KB Output is correct
11 Correct 101 ms 38840 KB Output is correct
12 Correct 164 ms 39492 KB Output is correct
13 Correct 84 ms 62272 KB Output is correct
14 Correct 99 ms 62464 KB Output is correct
15 Correct 151 ms 63120 KB Output is correct
16 Correct 241 ms 63900 KB Output is correct
17 Correct 245 ms 63552 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 441 ms 62008 KB Output is correct
2 Correct 440 ms 66104 KB Output is correct
3 Correct 439 ms 66012 KB Output is correct
4 Correct 423 ms 66136 KB Output is correct
5 Correct 453 ms 65960 KB Output is correct
6 Correct 386 ms 66036 KB Output is correct
7 Correct 490 ms 69180 KB Output is correct
8 Correct 487 ms 69108 KB Output is correct
9 Correct 457 ms 69176 KB Output is correct
10 Correct 428 ms 69152 KB Output is correct
11 Correct 433 ms 68756 KB Output is correct
12 Correct 418 ms 68116 KB Output is correct
13 Correct 459 ms 73528 KB Output is correct
14 Correct 471 ms 73676 KB Output is correct
15 Correct 457 ms 74052 KB Output is correct
16 Correct 464 ms 73672 KB Output is correct
17 Correct 541 ms 73052 KB Output is correct
18 Correct 457 ms 69796 KB Output is correct
19 Correct 592 ms 73572 KB Output is correct
20 Correct 571 ms 73536 KB Output is correct
21 Correct 566 ms 73844 KB Output is correct
22 Correct 551 ms 73784 KB Output is correct
23 Correct 508 ms 73004 KB Output is correct
24 Correct 511 ms 69656 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 18008 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 4 ms 18008 KB Output is correct
5 Correct 3 ms 18008 KB Output is correct
6 Correct 4 ms 18008 KB Output is correct
7 Correct 4 ms 18008 KB Output is correct
8 Correct 4 ms 18012 KB Output is correct
9 Correct 4 ms 18012 KB Output is correct
10 Correct 4 ms 18268 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 4 ms 18012 KB Output is correct
13 Correct 4 ms 18268 KB Output is correct
14 Correct 3 ms 18268 KB Output is correct
15 Correct 4 ms 18268 KB Output is correct
16 Correct 3 ms 18268 KB Output is correct
17 Correct 3 ms 18268 KB Output is correct
18 Correct 3 ms 18268 KB Output is correct
19 Correct 8 ms 18520 KB Output is correct
20 Correct 8 ms 18524 KB Output is correct
21 Correct 8 ms 18524 KB Output is correct
22 Correct 9 ms 18520 KB Output is correct
23 Correct 15 ms 19804 KB Output is correct
24 Correct 13 ms 19804 KB Output is correct
25 Correct 13 ms 19696 KB Output is correct
26 Correct 13 ms 20060 KB Output is correct
27 Correct 3 ms 18008 KB Output is correct
28 Correct 4 ms 18008 KB Output is correct
29 Correct 4 ms 18268 KB Output is correct
30 Correct 11 ms 18340 KB Output is correct
31 Correct 42 ms 18440 KB Output is correct
32 Correct 3 ms 18012 KB Output is correct
33 Correct 4 ms 18264 KB Output is correct
34 Correct 4 ms 18224 KB Output is correct
35 Correct 5 ms 18264 KB Output is correct
36 Correct 16 ms 18248 KB Output is correct
37 Correct 60 ms 18780 KB Output is correct
38 Correct 6 ms 19548 KB Output is correct
39 Correct 7 ms 19548 KB Output is correct
40 Correct 8 ms 19548 KB Output is correct
41 Correct 21 ms 19804 KB Output is correct
42 Correct 77 ms 20052 KB Output is correct
43 Correct 83 ms 59932 KB Output is correct
44 Correct 83 ms 59848 KB Output is correct
45 Correct 84 ms 59968 KB Output is correct
46 Correct 108 ms 60080 KB Output is correct
47 Correct 270 ms 60476 KB Output is correct
48 Correct 5 ms 18520 KB Output is correct
49 Correct 11 ms 18524 KB Output is correct
50 Correct 37 ms 18788 KB Output is correct
51 Correct 73 ms 19028 KB Output is correct
52 Correct 10 ms 21080 KB Output is correct
53 Correct 18 ms 21244 KB Output is correct
54 Correct 55 ms 21336 KB Output is correct
55 Correct 107 ms 21796 KB Output is correct
56 Correct 47 ms 37716 KB Output is correct
57 Correct 61 ms 37612 KB Output is correct
58 Correct 101 ms 38840 KB Output is correct
59 Correct 164 ms 39492 KB Output is correct
60 Correct 84 ms 62272 KB Output is correct
61 Correct 99 ms 62464 KB Output is correct
62 Correct 151 ms 63120 KB Output is correct
63 Correct 241 ms 63900 KB Output is correct
64 Correct 245 ms 63552 KB Output is correct
65 Correct 441 ms 62008 KB Output is correct
66 Correct 440 ms 66104 KB Output is correct
67 Correct 439 ms 66012 KB Output is correct
68 Correct 423 ms 66136 KB Output is correct
69 Correct 453 ms 65960 KB Output is correct
70 Correct 386 ms 66036 KB Output is correct
71 Correct 490 ms 69180 KB Output is correct
72 Correct 487 ms 69108 KB Output is correct
73 Correct 457 ms 69176 KB Output is correct
74 Correct 428 ms 69152 KB Output is correct
75 Correct 433 ms 68756 KB Output is correct
76 Correct 418 ms 68116 KB Output is correct
77 Correct 459 ms 73528 KB Output is correct
78 Correct 471 ms 73676 KB Output is correct
79 Correct 457 ms 74052 KB Output is correct
80 Correct 464 ms 73672 KB Output is correct
81 Correct 541 ms 73052 KB Output is correct
82 Correct 457 ms 69796 KB Output is correct
83 Correct 592 ms 73572 KB Output is correct
84 Correct 571 ms 73536 KB Output is correct
85 Correct 566 ms 73844 KB Output is correct
86 Correct 551 ms 73784 KB Output is correct
87 Correct 508 ms 73004 KB Output is correct
88 Correct 511 ms 69656 KB Output is correct
89 Correct 477 ms 65032 KB Output is correct
90 Correct 455 ms 65600 KB Output is correct
91 Correct 478 ms 67152 KB Output is correct
92 Correct 453 ms 66988 KB Output is correct
93 Correct 484 ms 69848 KB Output is correct
94 Correct 506 ms 68924 KB Output is correct
95 Correct 492 ms 70556 KB Output is correct
96 Correct 505 ms 69504 KB Output is correct
97 Correct 591 ms 70444 KB Output is correct
98 Correct 527 ms 73080 KB Output is correct
99 Correct 489 ms 70164 KB Output is correct
100 Correct 538 ms 70236 KB Output is correct