oj.uz

Submission #619296

# Submission time Handle Problem Language Result Execution time Memory
619296 2022-08-02T11:00:04 Z maximath_1 Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 5000 ms 112340 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int MX = 2e5 + 69;
const int LG = 18;
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], lz[MX];

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

	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;
		}
	}

	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]);
	}

	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];

	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]);
	}

	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];
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;
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];
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];

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:120:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |  scanf("%d %d %lld", &n, &q, &wtwtwt);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |   scanf("%d %d %lld", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:156:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   int ee; ll wt; scanf("%d %lld", &ee, &wt);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19152 KB Output is correct
3 Correct 12 ms 19124 KB Output is correct
4 Correct 12 ms 19220 KB Output is correct
5 Correct 12 ms 19172 KB Output is correct
6 Correct 9 ms 19156 KB Output is correct
7 Correct 12 ms 19260 KB Output is correct
8 Correct 10 ms 19284 KB Output is correct
9 Correct 12 ms 19244 KB Output is correct
10 Correct 10 ms 19276 KB Output is correct
11 Correct 11 ms 19284 KB Output is correct
12 Correct 10 ms 19284 KB Output is correct
13 Correct 14 ms 19284 KB Output is correct
14 Correct 14 ms 19284 KB Output is correct
15 Correct 11 ms 19280 KB Output is correct
16 Correct 11 ms 19280 KB Output is correct
17 Correct 11 ms 19284 KB Output is correct
18 Correct 15 ms 19232 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19152 KB Output is correct
3 Correct 12 ms 19124 KB Output is correct
4 Correct 12 ms 19220 KB Output is correct
5 Correct 12 ms 19172 KB Output is correct
6 Correct 9 ms 19156 KB Output is correct
7 Correct 12 ms 19260 KB Output is correct
8 Correct 10 ms 19284 KB Output is correct
9 Correct 12 ms 19244 KB Output is correct
10 Correct 10 ms 19276 KB Output is correct
11 Correct 11 ms 19284 KB Output is correct
12 Correct 10 ms 19284 KB Output is correct
13 Correct 14 ms 19284 KB Output is correct
14 Correct 14 ms 19284 KB Output is correct
15 Correct 11 ms 19280 KB Output is correct
16 Correct 11 ms 19280 KB Output is correct
17 Correct 11 ms 19284 KB Output is correct
18 Correct 15 ms 19232 KB Output is correct
19 Correct 34 ms 19920 KB Output is correct
20 Correct 37 ms 19924 KB Output is correct
21 Correct 49 ms 20136 KB Output is correct
22 Correct 46 ms 20088 KB Output is correct
23 Correct 61 ms 22568 KB Output is correct
24 Correct 77 ms 22932 KB Output is correct
25 Correct 90 ms 23160 KB Output is correct
26 Correct 98 ms 23684 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19124 KB Output is correct
2 Correct 10 ms 19156 KB Output is correct
3 Correct 14 ms 19160 KB Output is correct
4 Correct 30 ms 19272 KB Output is correct
5 Correct 105 ms 19548 KB Output is correct
6 Correct 11 ms 19164 KB Output is correct
7 Correct 12 ms 19328 KB Output is correct
8 Correct 11 ms 19368 KB Output is correct
9 Correct 15 ms 19388 KB Output is correct
10 Correct 39 ms 19492 KB Output is correct
11 Correct 127 ms 19860 KB Output is correct
12 Correct 22 ms 21460 KB Output is correct
13 Correct 18 ms 21424 KB Output is correct
14 Correct 21 ms 21532 KB Output is correct
15 Correct 47 ms 21560 KB Output is correct
16 Correct 166 ms 22004 KB Output is correct
17 Correct 175 ms 65032 KB Output is correct
18 Correct 175 ms 65004 KB Output is correct
19 Correct 204 ms 65072 KB Output is correct
20 Correct 251 ms 65164 KB Output is correct
21 Correct 586 ms 65676 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19924 KB Output is correct
2 Correct 54 ms 19992 KB Output is correct
3 Correct 217 ms 20208 KB Output is correct
4 Correct 395 ms 20516 KB Output is correct
5 Correct 56 ms 27020 KB Output is correct
6 Correct 107 ms 27100 KB Output is correct
7 Correct 592 ms 27260 KB Output is correct
8 Correct 745 ms 27640 KB Output is correct
9 Correct 259 ms 61632 KB Output is correct
10 Correct 398 ms 61724 KB Output is correct
11 Correct 818 ms 61948 KB Output is correct
12 Correct 1514 ms 62312 KB Output is correct
13 Correct 568 ms 107112 KB Output is correct
14 Correct 719 ms 107172 KB Output is correct
15 Correct 1276 ms 107360 KB Output is correct
16 Correct 1768 ms 107780 KB Output is correct
17 Correct 3268 ms 107672 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3087 ms 98112 KB Output is correct
2 Correct 3250 ms 99384 KB Output is correct
3 Correct 3064 ms 98996 KB Output is correct
4 Correct 3073 ms 99416 KB Output is correct
5 Correct 2908 ms 96808 KB Output is correct
6 Correct 2301 ms 85352 KB Output is correct
7 Correct 4444 ms 112268 KB Output is correct
8 Correct 4915 ms 112340 KB Output is correct
9 Execution timed out 5055 ms 112208 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Correct 12 ms 19152 KB Output is correct
3 Correct 12 ms 19124 KB Output is correct
4 Correct 12 ms 19220 KB Output is correct
5 Correct 12 ms 19172 KB Output is correct
6 Correct 9 ms 19156 KB Output is correct
7 Correct 12 ms 19260 KB Output is correct
8 Correct 10 ms 19284 KB Output is correct
9 Correct 12 ms 19244 KB Output is correct
10 Correct 10 ms 19276 KB Output is correct
11 Correct 11 ms 19284 KB Output is correct
12 Correct 10 ms 19284 KB Output is correct
13 Correct 14 ms 19284 KB Output is correct
14 Correct 14 ms 19284 KB Output is correct
15 Correct 11 ms 19280 KB Output is correct
16 Correct 11 ms 19280 KB Output is correct
17 Correct 11 ms 19284 KB Output is correct
18 Correct 15 ms 19232 KB Output is correct
19 Correct 34 ms 19920 KB Output is correct
20 Correct 37 ms 19924 KB Output is correct
21 Correct 49 ms 20136 KB Output is correct
22 Correct 46 ms 20088 KB Output is correct
23 Correct 61 ms 22568 KB Output is correct
24 Correct 77 ms 22932 KB Output is correct
25 Correct 90 ms 23160 KB Output is correct
26 Correct 98 ms 23684 KB Output is correct
27 Correct 13 ms 19124 KB Output is correct
28 Correct 10 ms 19156 KB Output is correct
29 Correct 14 ms 19160 KB Output is correct
30 Correct 30 ms 19272 KB Output is correct
31 Correct 105 ms 19548 KB Output is correct
32 Correct 11 ms 19164 KB Output is correct
33 Correct 12 ms 19328 KB Output is correct
34 Correct 11 ms 19368 KB Output is correct
35 Correct 15 ms 19388 KB Output is correct
36 Correct 39 ms 19492 KB Output is correct
37 Correct 127 ms 19860 KB Output is correct
38 Correct 22 ms 21460 KB Output is correct
39 Correct 18 ms 21424 KB Output is correct
40 Correct 21 ms 21532 KB Output is correct
41 Correct 47 ms 21560 KB Output is correct
42 Correct 166 ms 22004 KB Output is correct
43 Correct 175 ms 65032 KB Output is correct
44 Correct 175 ms 65004 KB Output is correct
45 Correct 204 ms 65072 KB Output is correct
46 Correct 251 ms 65164 KB Output is correct
47 Correct 586 ms 65676 KB Output is correct
48 Correct 19 ms 19924 KB Output is correct
49 Correct 54 ms 19992 KB Output is correct
50 Correct 217 ms 20208 KB Output is correct
51 Correct 395 ms 20516 KB Output is correct
52 Correct 56 ms 27020 KB Output is correct
53 Correct 107 ms 27100 KB Output is correct
54 Correct 592 ms 27260 KB Output is correct
55 Correct 745 ms 27640 KB Output is correct
56 Correct 259 ms 61632 KB Output is correct
57 Correct 398 ms 61724 KB Output is correct
58 Correct 818 ms 61948 KB Output is correct
59 Correct 1514 ms 62312 KB Output is correct
60 Correct 568 ms 107112 KB Output is correct
61 Correct 719 ms 107172 KB Output is correct
62 Correct 1276 ms 107360 KB Output is correct
63 Correct 1768 ms 107780 KB Output is correct
64 Correct 3268 ms 107672 KB Output is correct
65 Correct 3087 ms 98112 KB Output is correct
66 Correct 3250 ms 99384 KB Output is correct
67 Correct 3064 ms 98996 KB Output is correct
68 Correct 3073 ms 99416 KB Output is correct
69 Correct 2908 ms 96808 KB Output is correct
70 Correct 2301 ms 85352 KB Output is correct
71 Correct 4444 ms 112268 KB Output is correct
72 Correct 4915 ms 112340 KB Output is correct
73 Execution timed out 5055 ms 112208 KB Time limit exceeded
74 Halted 0 ms 0 KB -