oj.uz

Submission #276006

# Submission time Handle Problem Language Result Execution time Memory
276006 2020-08-20T09:19:19 Z theStaticMind Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 931 ms 30944 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
int S;
struct MaxSeg{
	vector<int> seg;
	vector<int> lazy;

	MaxSeg(int N);
	void build();
	void push(int j);
	void pull(int j);
	void rangeupdate(int j, int x, int y, int l, int r, int v);
	int rangequery(int j, int x, int y, int l, int r);
} seg(100005);


int n;

vector<ii> adj[100005];
vector<ii> edge;
int anc[100005];
int depth[100005];
int T[100005];
int X[100005];

multiset<int> data;
map<int, int> ptr;

int getedge(int x, int y){
	return lower_bound(all(adj[x]), ii{y, -1}) - adj[x].begin();
}

void update(int y){
	data.erase(data.lower_bound(ptr[y]));
	ptr[y] = seg.rangequery(1, 0, S - 1, T[y], X[y]);
	data.insert(ptr[y]);
}

void init(int x, int pre){
	static int time = 1;
	T[x] = time++;
	
	if(pre == 1)anc[x] = x;
	
	for(auto p : adj[x]){
		int y = p.first;
		if(y == pre) continue;
		
		anc[y] = anc[x];
		depth[y] = depth[x] + 1;

		init(y, x);

	}
	X[x] = time - 1;
}


vector<int> dp(100005, 0);
void naive(int x, int pre){

	for(auto p : adj[x]){
		int y = p.first;
		if(y == pre) continue;
		
		dp[y] = dp[x] + p.second;

		naive(y, x);

	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int q, W;
	cin >> n >> q >> W;

	for(int i = 0; i < n - 1; i++){
		int x, y, z;
		cin >> x >> y >> z;
		adj[x].pb({y, z});
		adj[y].pb({x, z});

		edge.pb({x, y});
	}

	for(int i = 1; i <= n; i++){
		sort(all(adj[i]));
	}

	init(1, 0);
	naive(1, 0);

	for(int i = 1; i <= n; i++){
		seg.rangeupdate(1, 0, S - 1, T[i], T[i], dp[i]);
	}

	int last = 0;

	for(auto p : adj[1]){
		ptr[p.first] = seg.rangequery(1, 0, S - 1, T[p.first], X[p.first]);
		data.insert(ptr[p.first]);
	}

	while(q--){ 
		ii p;
		cin >> p.first >> p.second;
		p.first = (p.first + last) % (n - 1);
		p.second = (p.second + last) % W;
		int x = edge[p.first].first;
		int y = edge[p.first].second;
		int z = p.second;

		if(depth[x] > depth[y]) swap(x, y);
		
		seg.rangeupdate(1, 0, S - 1, T[y], X[y], z - adj[x][getedge(x, y)].second);
		update(anc[y]);
		
		adj[x][getedge(x, y)].second = z;
		adj[y][getedge(y, x)].second = z;

		last = *data.rbegin();
		if(sz(data) > 1)  last += *++data.rbegin();

		cout << last << "\n";
	}
}

MaxSeg::MaxSeg(int N){
	seg= vector<int>(N, 0);
	build();
}

void MaxSeg::build(){
	S = 1 << (int)ceil(log2(sz(seg)));
	while(sz(seg) != S) seg.pb(0);
	reverse(all(seg));
	for(int i = 1; i < sz(seg); i += 2) seg.pb(max(seg[i - 1], seg[i]));
	seg.pb(0);
	reverse(all(seg));
	lazy = vector<int> (sz(seg), 0);
}

void MaxSeg::push(int j){
	if(j < sz(seg)){
		seg[j] += lazy[j];
		if(j * 2 < sz(seg)){
			lazy[j*2] += lazy[j];
			lazy[j*2+1] += lazy[j];
		}
		lazy[j] = 0;
	}
}

void MaxSeg::pull(int j){
	push(j);
	push(j*2);
	push(j*2+1);
	if(j * 2 < sz(seg)){
		seg[j] = max(seg[j*2], seg[j*2+1]);
	}
}

void MaxSeg::rangeupdate(int j, int x, int y, int l, int r, int v){
	if(y < l || r < x) return;
	push(j);
	if(l <= x && y <= r){
		lazy[j] += v;
	}
	else{
		rangeupdate(j*2,x,(x+y)/2,l,r,v);
		rangeupdate(j*2+1,(x+y)/2+1,y,l,r,v);
	}
	pull(j);
}

int MaxSeg::rangequery(int j, int x, int y, int l, int r){
	if(y < l || r < x) return 0;
	push(j);
	if(l <= x && y <= r){
		return seg[j];
	}
	else{
		return max(
			rangequery(j*2,x,(x+y)/2,l,r),
			rangequery(j*2+1,(x+y)/2+1,y,l,r)
			);
	}
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7636 KB Output is correct
2 Correct 9 ms 7636 KB Output is correct
3 Correct 10 ms 7636 KB Output is correct
4 Correct 37 ms 7880 KB Output is correct
5 Correct 158 ms 8028 KB Output is correct
6 Correct 6 ms 7636 KB Output is correct
7 Correct 7 ms 7764 KB Output is correct
8 Correct 8 ms 7764 KB Output is correct
9 Correct 12 ms 7688 KB Output is correct
10 Correct 45 ms 7796 KB Output is correct
11 Correct 197 ms 8136 KB Output is correct
12 Correct 19 ms 8660 KB Output is correct
13 Correct 18 ms 8660 KB Output is correct
14 Correct 22 ms 8660 KB Output is correct
15 Correct 75 ms 8740 KB Output is correct
16 Correct 270 ms 9176 KB Output is correct
17 Correct 263 ms 27888 KB Output is correct
18 Correct 265 ms 27956 KB Output is correct
19 Correct 305 ms 27976 KB Output is correct
20 Correct 345 ms 28128 KB Output is correct
21 Correct 931 ms 28616 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 19156 KB Output is correct
2 Correct 490 ms 23232 KB Output is correct
3 Correct 536 ms 23336 KB Output is correct
4 Correct 515 ms 23368 KB Output is correct
5 Correct 496 ms 24116 KB Output is correct
6 Correct 519 ms 28392 KB Output is correct
7 Correct 510 ms 25120 KB Output is correct
8 Correct 517 ms 25196 KB Output is correct
9 Correct 521 ms 25288 KB Output is correct
10 Correct 550 ms 25288 KB Output is correct
11 Correct 562 ms 25928 KB Output is correct
12 Correct 583 ms 29700 KB Output is correct
13 Correct 538 ms 27976 KB Output is correct
14 Correct 533 ms 28100 KB Output is correct
15 Correct 543 ms 27724 KB Output is correct
16 Correct 548 ms 27892 KB Output is correct
17 Correct 567 ms 28360 KB Output is correct
18 Correct 560 ms 30944 KB Output is correct
19 Correct 537 ms 27832 KB Output is correct
20 Correct 532 ms 27848 KB Output is correct
21 Correct 552 ms 27912 KB Output is correct
22 Correct 595 ms 27848 KB Output is correct
23 Correct 610 ms 28488 KB Output is correct
24 Correct 617 ms 30788 KB Output is correct

Subtask #6
0 / 27.0

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