oj.uz

Submission #619341

# Submission time Handle Problem Language Result Execution time Memory
619341 2022-08-02T11:15:58 Z maximath_1 Dynamic Diameter (CEOI19_diameter) C++11
100 / 100
 4670 ms 108056 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

#define ll long long
const int MX = 1e5 + 69;
const int LG = 17;
const ll inf = 4e18 + 69;
#define ll long long
int n, q; ll wtwtwt;
vector<pair<pair<int, int>, ll> > edges;
vector<int> adj[MX];

struct SegmentTree{
	ll st[MX * 2], lz[MX * 2];

	#define cm (cl + cr) / 2
	#define lc nd + 1
	#define rc nd + 2 * (cm - cl + 1)

	inline void prop(int nd, int cl, int cr){
		if(lz[nd]){
			st[nd] += lz[nd];
			if(cl != cr){
				lz[lc] += lz[nd];
				lz[rc] += lz[nd];
			}
			lz[nd] = 0;
		}
	}

	inline void upd(int nd, int cl, int cr, int lf, int rg, ll vl){
		prop(nd, cl, cr);
		if(cr < lf || rg < cl) return;
		if(lf <= cl && cr <= rg){
			lz[nd] += vl;
			prop(nd, cl, cr);
			return;
		}

		upd(lc, cl, cm, lf, rg, vl);
		upd(rc, cm + 1, cr, lf, rg, vl);
		st[nd] = max(st[lc], st[rc]);
	}

	inline ll que(int nd, int cl, int cr, int lf, int rg){
		prop(nd, cl, cr);
		if(cr < lf || rg < cl) return -1;
		if(lf <= cl && cr <= rg) return st[nd];
		ll L = que(lc, cl, cm, lf, rg);
		ll R = que(rc, cm + 1, cr, lf, rg);
		return max(L, R);
	}
} st[LG];

struct SegmentTreeIterative{
	ll st[MX << 1];

	inline void upd(int ps, ll vl){
		for(ps += MX, st[ps] = vl, ps >>= 1; ps > 0; ps >>= 1) st[ps] = max(st[ps << 1], st[ps << 1 | 1]);
	}

	inline ll que(ll lf, ll rg){
		ll rs = 0ll;
		for(lf += MX, rg += MX + 1; lf < rg; lf >>= 1, rg >>= 1){
			if(lf & 1) rs = max(st[lf ++], rs);
			if(rg & 1) rs = max(rs, st[-- rg]);
		}
		return rs;
	}
} stdp;

bool vis[MX], dead[MX];
int sz[MX];
inline void dfssz(int nw, int bf){
	sz[nw] = 1;
	for(int nx : adj[nw]) if(nx != bf && !dead[nx]){
		dfssz(nx, nw);
		sz[nw] += sz[nx];
	}
}

int cent = -1, ccsz = 0;
inline void dfscent(int nw, int bf){
	for(int nx : adj[nw]) if(nx != bf && !dead[nx]) dfscent(nx, nw);
	if(cent == -1 && sz[nw] >= (ccsz + 1) / 2) cent = nw;
}

int layer = 0, tin[MX][LG], tim[LG], tout[MX][LG], rt[MX][LG], par[MX][LG], layer_id[MX];
inline void init(int nw, int bf){
	rt[nw][layer] = cent;
	tin[nw][layer] = ++ tim[layer];
	par[nw][layer] = bf;
	for(int nx : adj[nw]) if(nx != bf && !dead[nx]) init(nx, nw);
	tout[nw][layer] = tim[layer];
}

vector<pair<int, int> > adj_root[MX];

inline void findCentroid(int nw){
	dfssz(nw, 0);
	cent = -1, ccsz = sz[nw];
	dfscent(nw, 0);

	init(cent, 0); layer_id[cent] = layer;
	for(int nx : adj[cent]) if(!dead[nx])
		adj_root[cent].push_back({tin[nx][layer], nx});
	sort(adj_root[cent].begin(), adj_root[cent].end());

	dead[cent] = 1;
	for(int nx : adj[cent]) if(!dead[nx]){
		layer ++;
		findCentroid(nx);
		layer --;
	}
}

set<pair<ll, int> > dp[MX];

int main(){
	scanf("%d %d %lld", &n, &q, &wtwtwt);
	for(int i = 1; i < n; i ++){
		int u, v; ll w;
		scanf("%d %d %lld", &u, &v, &w);
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back({{u, v}, w});
	}

	findCentroid(1);

	for(auto e : edges){
		int u = e.first.first, v = e.first.second; ll w = e.second;
		for(int j = 0; j < LG; j ++){
			if(rt[u][j] != rt[v][j]) break;
			if(tin[u][j] < tin[v][j]) swap(u, v);
			st[j].upd(1, 1, n, tin[u][j], tout[u][j], w);
		}
	}

	for(int i = 1; i <= n; i ++){
		for(pair<int, int> nx : adj_root[i])
			dp[i].insert({st[layer_id[i]].que(1, 1, n, tin[nx.second][layer_id[i]], tout[nx.second][layer_id[i]]), tin[nx.second][layer_id[i]]});

		ll res = 0ll;
		auto it = dp[i].end();
		for(int _ = 0; _ < 2; _ ++) if(it != dp[i].begin()){
			it = prev(it);
			res += (*it).first;
		}

		stdp.upd(i, res);
	}

	ll last_answer = 0ll;
	for(; q --;){
		int ee; ll wt; scanf("%d %lld", &ee, &wt);
		ee = (int)((ee + last_answer) % (n - 1));
		wt = (wt + last_answer) % wtwtwt;

		int u = edges[ee].first.first, v = edges[ee].first.second; ll wtchange = wt - edges[ee].second;

		for(int j = 0; j < LG; j ++){
			if(rt[u][j] != rt[v][j]) break;
			if(tin[u][j] < tin[v][j]) swap(u, v);
			int uid = lower_bound(adj_root[rt[u][j]].begin(), adj_root[rt[u][j]].end(), make_pair(tin[u][j] + 1, -1)) - adj_root[rt[u][j]].begin();
			int anc = adj_root[rt[u][j]][uid - 1].second;

			dp[rt[u][j]].erase(make_pair(st[j].que(1, 1, n, tin[anc][j], tout[anc][j]), tin[anc][j]));
			st[j].upd(1, 1, n, tin[u][j], tout[u][j], wtchange);
			dp[rt[u][j]].insert(make_pair(st[j].que(1, 1, n, tin[anc][j], tout[anc][j]), tin[anc][j]));

			ll res = 0ll;
			auto it = dp[rt[u][j]].end();
			for(int _ = 0; _ < 2; _ ++) if(it != dp[rt[u][j]].begin()){
				it = prev(it);
				res += (*it).first;
			}

			stdp.upd(rt[u][j], res);
		}

		edges[ee].second = wt;

		last_answer = stdp.que(1, n);
		printf("%lld\n", last_answer);
	}

	return 0;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  scanf("%d %d %lld", &n, &q, &wtwtwt);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |   scanf("%d %d %lld", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:157:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   int ee; ll wt; scanf("%d %lld", &ee, &wt);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9780 KB Output is correct
5 Correct 5 ms 9716 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 30 ms 10520 KB Output is correct
20 Correct 26 ms 10452 KB Output is correct
21 Correct 35 ms 10576 KB Output is correct
22 Correct 35 ms 10628 KB Output is correct
23 Correct 42 ms 13052 KB Output is correct
24 Correct 57 ms 13432 KB Output is correct
25 Correct 63 ms 13640 KB Output is correct
26 Correct 93 ms 13900 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9764 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 8 ms 9812 KB Output is correct
4 Correct 19 ms 9896 KB Output is correct
5 Correct 72 ms 10156 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9928 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 8 ms 9920 KB Output is correct
10 Correct 25 ms 10084 KB Output is correct
11 Correct 114 ms 10396 KB Output is correct
12 Correct 10 ms 11972 KB Output is correct
13 Correct 10 ms 11996 KB Output is correct
14 Correct 12 ms 11988 KB Output is correct
15 Correct 36 ms 12132 KB Output is correct
16 Correct 141 ms 12404 KB Output is correct
17 Correct 149 ms 54012 KB Output is correct
18 Correct 127 ms 53948 KB Output is correct
19 Correct 133 ms 53980 KB Output is correct
20 Correct 218 ms 54100 KB Output is correct
21 Correct 421 ms 54584 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10452 KB Output is correct
2 Correct 39 ms 10568 KB Output is correct
3 Correct 170 ms 10756 KB Output is correct
4 Correct 336 ms 11024 KB Output is correct
5 Correct 40 ms 17480 KB Output is correct
6 Correct 87 ms 17484 KB Output is correct
7 Correct 312 ms 17736 KB Output is correct
8 Correct 607 ms 18288 KB Output is correct
9 Correct 197 ms 51480 KB Output is correct
10 Correct 330 ms 51768 KB Output is correct
11 Correct 706 ms 51832 KB Output is correct
12 Correct 1120 ms 52184 KB Output is correct
13 Correct 415 ms 96100 KB Output is correct
14 Correct 594 ms 96152 KB Output is correct
15 Correct 1185 ms 96556 KB Output is correct
16 Correct 1584 ms 96616 KB Output is correct
17 Correct 2773 ms 96652 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2455 ms 87108 KB Output is correct
2 Correct 2587 ms 88360 KB Output is correct
3 Correct 2571 ms 88004 KB Output is correct
4 Correct 2568 ms 88344 KB Output is correct
5 Correct 2500 ms 85884 KB Output is correct
6 Correct 2130 ms 74196 KB Output is correct
7 Correct 3859 ms 99460 KB Output is correct
8 Correct 3691 ms 99420 KB Output is correct
9 Correct 3649 ms 99540 KB Output is correct
10 Correct 3649 ms 99220 KB Output is correct
11 Correct 3639 ms 96384 KB Output is correct
12 Correct 2933 ms 80300 KB Output is correct
13 Correct 4022 ms 104852 KB Output is correct
14 Correct 4062 ms 104712 KB Output is correct
15 Correct 3849 ms 104836 KB Output is correct
16 Correct 3947 ms 104472 KB Output is correct
17 Correct 3717 ms 100612 KB Output is correct
18 Correct 3525 ms 81784 KB Output is correct
19 Correct 4394 ms 104820 KB Output is correct
20 Correct 3963 ms 104700 KB Output is correct
21 Correct 4029 ms 104732 KB Output is correct
22 Correct 4003 ms 104536 KB Output is correct
23 Correct 3790 ms 100844 KB Output is correct
24 Correct 3040 ms 81800 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9780 KB Output is correct
5 Correct 5 ms 9716 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 30 ms 10520 KB Output is correct
20 Correct 26 ms 10452 KB Output is correct
21 Correct 35 ms 10576 KB Output is correct
22 Correct 35 ms 10628 KB Output is correct
23 Correct 42 ms 13052 KB Output is correct
24 Correct 57 ms 13432 KB Output is correct
25 Correct 63 ms 13640 KB Output is correct
26 Correct 93 ms 13900 KB Output is correct
27 Correct 5 ms 9764 KB Output is correct
28 Correct 5 ms 9684 KB Output is correct
29 Correct 8 ms 9812 KB Output is correct
30 Correct 19 ms 9896 KB Output is correct
31 Correct 72 ms 10156 KB Output is correct
32 Correct 5 ms 9684 KB Output is correct
33 Correct 6 ms 9928 KB Output is correct
34 Correct 5 ms 9940 KB Output is correct
35 Correct 8 ms 9920 KB Output is correct
36 Correct 25 ms 10084 KB Output is correct
37 Correct 114 ms 10396 KB Output is correct
38 Correct 10 ms 11972 KB Output is correct
39 Correct 10 ms 11996 KB Output is correct
40 Correct 12 ms 11988 KB Output is correct
41 Correct 36 ms 12132 KB Output is correct
42 Correct 141 ms 12404 KB Output is correct
43 Correct 149 ms 54012 KB Output is correct
44 Correct 127 ms 53948 KB Output is correct
45 Correct 133 ms 53980 KB Output is correct
46 Correct 218 ms 54100 KB Output is correct
47 Correct 421 ms 54584 KB Output is correct
48 Correct 12 ms 10452 KB Output is correct
49 Correct 39 ms 10568 KB Output is correct
50 Correct 170 ms 10756 KB Output is correct
51 Correct 336 ms 11024 KB Output is correct
52 Correct 40 ms 17480 KB Output is correct
53 Correct 87 ms 17484 KB Output is correct
54 Correct 312 ms 17736 KB Output is correct
55 Correct 607 ms 18288 KB Output is correct
56 Correct 197 ms 51480 KB Output is correct
57 Correct 330 ms 51768 KB Output is correct
58 Correct 706 ms 51832 KB Output is correct
59 Correct 1120 ms 52184 KB Output is correct
60 Correct 415 ms 96100 KB Output is correct
61 Correct 594 ms 96152 KB Output is correct
62 Correct 1185 ms 96556 KB Output is correct
63 Correct 1584 ms 96616 KB Output is correct
64 Correct 2773 ms 96652 KB Output is correct
65 Correct 2455 ms 87108 KB Output is correct
66 Correct 2587 ms 88360 KB Output is correct
67 Correct 2571 ms 88004 KB Output is correct
68 Correct 2568 ms 88344 KB Output is correct
69 Correct 2500 ms 85884 KB Output is correct
70 Correct 2130 ms 74196 KB Output is correct
71 Correct 3859 ms 99460 KB Output is correct
72 Correct 3691 ms 99420 KB Output is correct
73 Correct 3649 ms 99540 KB Output is correct
74 Correct 3649 ms 99220 KB Output is correct
75 Correct 3639 ms 96384 KB Output is correct
76 Correct 2933 ms 80300 KB Output is correct
77 Correct 4022 ms 104852 KB Output is correct
78 Correct 4062 ms 104712 KB Output is correct
79 Correct 3849 ms 104836 KB Output is correct
80 Correct 3947 ms 104472 KB Output is correct
81 Correct 3717 ms 100612 KB Output is correct
82 Correct 3525 ms 81784 KB Output is correct
83 Correct 4394 ms 104820 KB Output is correct
84 Correct 3963 ms 104700 KB Output is correct
85 Correct 4029 ms 104732 KB Output is correct
86 Correct 4003 ms 104536 KB Output is correct
87 Correct 3790 ms 100844 KB Output is correct
88 Correct 3040 ms 81800 KB Output is correct
89 Correct 2459 ms 87428 KB Output is correct
90 Correct 3186 ms 95464 KB Output is correct
91 Correct 4539 ms 101156 KB Output is correct
92 Correct 4173 ms 102508 KB Output is correct
93 Correct 4670 ms 104948 KB Output is correct
94 Correct 4138 ms 105204 KB Output is correct
95 Correct 4147 ms 107052 KB Output is correct
96 Correct 4009 ms 106668 KB Output is correct
97 Correct 3995 ms 107124 KB Output is correct
98 Correct 3874 ms 108056 KB Output is correct
99 Correct 4030 ms 106928 KB Output is correct
100 Correct 4147 ms 107072 KB Output is correct