oj.uz

Submission #619293

# Submission time Handle Problem Language Result Execution time Memory
619293 2022-08-02T10:59:11 Z maximath_1 Dynamic Diameter (CEOI19_diameter) C++11
24 / 100
 3311 ms 94672 KB 
#include <bits/stdc++.h>
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], 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 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9760 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9832 KB Output is correct
11 Correct 6 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 5 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 5 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 5 ms 9812 KB Output is correct
3 Correct 5 ms 9760 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9832 KB Output is correct
11 Correct 6 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 5 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 5 ms 9812 KB Output is correct
19 Correct 25 ms 10480 KB Output is correct
20 Correct 28 ms 10620 KB Output is correct
21 Correct 33 ms 10568 KB Output is correct
22 Correct 38 ms 10612 KB Output is correct
23 Correct 42 ms 13044 KB Output is correct
24 Correct 57 ms 13400 KB Output is correct
25 Correct 63 ms 13524 KB Output is correct
26 Correct 77 ms 14096 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9780 KB Output is correct
4 Correct 20 ms 9848 KB Output is correct
5 Correct 74 ms 10140 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 8 ms 9980 KB Output is correct
10 Correct 26 ms 10036 KB Output is correct
11 Correct 105 ms 10388 KB Output is correct
12 Correct 11 ms 11980 KB Output is correct
13 Correct 11 ms 11992 KB Output is correct
14 Correct 13 ms 11988 KB Output is correct
15 Correct 36 ms 12116 KB Output is correct
16 Correct 137 ms 12444 KB Output is correct
17 Incorrect 122 ms 53252 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10532 KB Output is correct
2 Correct 39 ms 10580 KB Output is correct
3 Correct 177 ms 10828 KB Output is correct
4 Correct 329 ms 11052 KB Output is correct
5 Correct 44 ms 17420 KB Output is correct
6 Correct 98 ms 17480 KB Output is correct
7 Correct 339 ms 17768 KB Output is correct
8 Correct 657 ms 18080 KB Output is correct
9 Correct 233 ms 51336 KB Output is correct
10 Correct 346 ms 51504 KB Output is correct
11 Correct 749 ms 51748 KB Output is correct
12 Correct 1264 ms 52044 KB Output is correct
13 Incorrect 516 ms 75456 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 3311 ms 94672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9760 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9832 KB Output is correct
11 Correct 6 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 5 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 5 ms 9812 KB Output is correct
19 Correct 25 ms 10480 KB Output is correct
20 Correct 28 ms 10620 KB Output is correct
21 Correct 33 ms 10568 KB Output is correct
22 Correct 38 ms 10612 KB Output is correct
23 Correct 42 ms 13044 KB Output is correct
24 Correct 57 ms 13400 KB Output is correct
25 Correct 63 ms 13524 KB Output is correct
26 Correct 77 ms 14096 KB Output is correct
27 Correct 6 ms 9684 KB Output is correct
28 Correct 6 ms 9684 KB Output is correct
29 Correct 6 ms 9780 KB Output is correct
30 Correct 20 ms 9848 KB Output is correct
31 Correct 74 ms 10140 KB Output is correct
32 Correct 6 ms 9684 KB Output is correct
33 Correct 5 ms 9940 KB Output is correct
34 Correct 7 ms 9940 KB Output is correct
35 Correct 8 ms 9980 KB Output is correct
36 Correct 26 ms 10036 KB Output is correct
37 Correct 105 ms 10388 KB Output is correct
38 Correct 11 ms 11980 KB Output is correct
39 Correct 11 ms 11992 KB Output is correct
40 Correct 13 ms 11988 KB Output is correct
41 Correct 36 ms 12116 KB Output is correct
42 Correct 137 ms 12444 KB Output is correct
43 Incorrect 122 ms 53252 KB Output isn't correct
44 Halted 0 ms 0 KB -