oj.uz

Submission #619276

# Submission time Handle Problem Language Result Execution time Memory
619276 2022-08-02T10:53:48 Z maximath_1 Dynamic Diameter (CEOI19_diameter) C++11
24 / 100
 4386 ms 114432 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int MX = 1e5 + 5;
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; cin >> 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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9700 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9740 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 5 ms 9776 KB Output is correct
9 Correct 6 ms 9744 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 6 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 6 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 6 ms 9684 KB Output is correct
2 Correct 7 ms 9700 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9740 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 5 ms 9776 KB Output is correct
9 Correct 6 ms 9744 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 6 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 6 ms 9812 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 33 ms 10452 KB Output is correct
20 Correct 36 ms 10488 KB Output is correct
21 Correct 39 ms 10552 KB Output is correct
22 Correct 57 ms 10620 KB Output is correct
23 Correct 55 ms 13012 KB Output is correct
24 Correct 66 ms 13384 KB Output is correct
25 Correct 73 ms 13608 KB Output is correct
26 Correct 79 ms 14156 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9780 KB Output is correct
3 Correct 14 ms 9776 KB Output is correct
4 Correct 54 ms 9852 KB Output is correct
5 Correct 225 ms 10192 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 7 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 12 ms 9940 KB Output is correct
10 Correct 58 ms 10028 KB Output is correct
11 Correct 284 ms 10436 KB Output is correct
12 Correct 11 ms 11988 KB Output is correct
13 Correct 11 ms 11988 KB Output is correct
14 Correct 16 ms 12008 KB Output is correct
15 Correct 70 ms 12036 KB Output is correct
16 Correct 293 ms 12500 KB Output is correct
17 Incorrect 155 ms 53304 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10520 KB Output is correct
2 Correct 57 ms 10636 KB Output is correct
3 Correct 251 ms 10740 KB Output is correct
4 Correct 487 ms 11176 KB Output is correct
5 Correct 45 ms 17480 KB Output is correct
6 Correct 117 ms 17528 KB Output is correct
7 Correct 439 ms 17684 KB Output is correct
8 Correct 837 ms 18044 KB Output is correct
9 Correct 252 ms 51464 KB Output is correct
10 Correct 365 ms 51488 KB Output is correct
11 Correct 835 ms 51724 KB Output is correct
12 Correct 1484 ms 52020 KB Output is correct
13 Incorrect 514 ms 75528 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9700 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9740 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 5 ms 9776 KB Output is correct
9 Correct 6 ms 9744 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 6 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 6 ms 9812 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 33 ms 10452 KB Output is correct
20 Correct 36 ms 10488 KB Output is correct
21 Correct 39 ms 10552 KB Output is correct
22 Correct 57 ms 10620 KB Output is correct
23 Correct 55 ms 13012 KB Output is correct
24 Correct 66 ms 13384 KB Output is correct
25 Correct 73 ms 13608 KB Output is correct
26 Correct 79 ms 14156 KB Output is correct
27 Correct 5 ms 9684 KB Output is correct
28 Correct 7 ms 9780 KB Output is correct
29 Correct 14 ms 9776 KB Output is correct
30 Correct 54 ms 9852 KB Output is correct
31 Correct 225 ms 10192 KB Output is correct
32 Correct 5 ms 9684 KB Output is correct
33 Correct 7 ms 9940 KB Output is correct
34 Correct 6 ms 9940 KB Output is correct
35 Correct 12 ms 9940 KB Output is correct
36 Correct 58 ms 10028 KB Output is correct
37 Correct 284 ms 10436 KB Output is correct
38 Correct 11 ms 11988 KB Output is correct
39 Correct 11 ms 11988 KB Output is correct
40 Correct 16 ms 12008 KB Output is correct
41 Correct 70 ms 12036 KB Output is correct
42 Correct 293 ms 12500 KB Output is correct
43 Incorrect 155 ms 53304 KB Output isn't correct
44 Halted 0 ms 0 KB -