oj.uz

Submission #619039

# Submission time Handle Problem Language Result Execution time Memory
619039 2022-08-02T09:25:59 Z HappyPacMan Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 415144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
using ll = long long;
const int maxn = 1e5 + 3;
vector<pair<int,int> > adj[maxn],edges;
vector<int> partOf[maxn];
vector<ll> seg[maxn],lazy[maxn];
bool isCent[maxn];
int subSz[maxn],centRoot,timer[maxn];
unordered_map<int,int> tin[maxn],tout[maxn],edgeRoot[maxn];
set<pair<int,ll> > bestEdge[maxn],result; 
ll cost[maxn];

void dfsSz(int u,int p){
	subSz[u] = 1;
	for(auto [v,w] : adj[u]){
		if(v != p && !isCent[v]){
			dfsSz(v,u);
			subSz[u] += subSz[v];
		}
	}
}
int fnCent(int u,int p,int s){
	for(auto [v,w] : adj[u]){
		if(v != p && !isCent[v] && subSz[v] > s/2){
			return fnCent(v,u,s);
		}
	}
	return u;
}
void dfsTour(int c,int u,int p){
	for(auto [v,w] : adj[u]){
		if(v != p && !isCent[v]){
			partOf[w].emplace_back(c);
			tin[c][w] = timer[c]++;
			dfsTour(c,v,u);
			tout[c][w] = timer[c]++;
		}
	}
}
void dfsEdgeRoot(int c,int d,int u,int p){
	for(auto [v,w] : adj[u]){
		if(v != p && !isCent[v]){
			edgeRoot[c][w] = d;
			dfsEdgeRoot(c,d,v,u);
		}
	}
}
void dfsCent(int u,int p){
	dfsSz(u,p);
	int cent = fnCent(u,u,subSz[u]);
	isCent[cent] = true;
	if(p != -1){
		centRoot = cent;
	}
	dfsTour(cent,cent,cent);
	for(auto [v,w] : adj[cent]){
		if(!isCent[v]){
			bestEdge[cent].emplace(0,w);
			edgeRoot[cent][w] = w;
			dfsEdgeRoot(cent,w,v,cent);
		}
	}
	seg[cent].resize(4*timer[cent]);
	lazy[cent].resize(4*timer[cent]);
	for(auto [v,w] : adj[cent]){
		if(!isCent[v]){
			dfsCent(v,cent);
		}
	}
}

// Segment Tree + Lazy Propagation
void push(int c,int i){
	lazy[c][i<<1] += lazy[c][i];
	seg[c][i<<1] += lazy[c][i];
	lazy[c][i<<1|1] += lazy[c][i];
	seg[c][i<<1|1] += lazy[c][i];
	lazy[c][i] = 0;
}
void upd(int c,int i,int l,int r,int ul,int ur,ll v){
	if(ul <= l && r <= ur){
		seg[c][i] += v;
		lazy[c][i] += v;
	}else if(ul > r || ur < l){
		return;
	}else{
		int m = (l+r)/2;
		push(c,i);
		upd(c,i<<1,l,m,ul,ur,v);
		upd(c,i<<1|1,m+1,r,ul,ur,v);
		seg[c][i] = max(seg[c][i<<1],seg[c][i<<1|1]);
	}
}
ll qry(int c,int i,int l,int r,int ql,int qr){
	if(ql <= l && r <= qr){
		return seg[c][i];
	}else if(ql > r || qr < l){
		return 0;
	}else{
		int m = (l+r)/2;
		push(c,i);
		return max(qry(c,i<<1,l,m,ql,qr),qry(c,i<<1|1,m+1,r,ql,qr));
	}
}

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

	int n,q;
	ll w;
	cin >> n >> q >> w;
	for(int i=1;i<n;i++){
		int u,v;
		ll w;
		cin >> u >> v >> w;
		u--; v--;
		adj[u].emplace_back(v,i);
		adj[v].emplace_back(u,i);
		edges.emplace_back(u,v);
		cost[i] = w;
	}
	dfsCent(0,-1);
	for(int i=1;i<n;i++){
		for(int it : partOf[i]){
			bestEdge[it].erase(bestEdge[it].find(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i])));
			upd(it,1,0,timer[it]-1,tin[it][i],timer[it]-1,cost[i]);
			upd(it,1,0,timer[it]-1,tout[it][i],timer[it]-1,-cost[i]);
			bestEdge[it].insert(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i]));
		}
	}
	for(int i=0;i<n;i++){
		if(bestEdge[i].size() > 1){
			result.emplace((*prev(bestEdge[i].end())).first+(*prev(prev(bestEdge[i].end()))).first,i);
		}else if(bestEdge[i].size()){
			result.emplace((*prev(bestEdge[i].end())).first,i);
		}else{
			result.emplace(0,i);
		}
	}
	ll last = 0;
	while(q--){
		int i;
		ll j;
		cin >> i >> j;
		i = (i+last)%(n-1)+1;
		j = (j+last)%w;
		ll df = j-cost[i];
		for(int it : partOf[i]){
			if(bestEdge[it].size() > 1){
				result.erase(result.find(make_pair((*prev(bestEdge[it].end())).first+(*prev(prev(bestEdge[it].end()))).first,it)));
			}else if(bestEdge[it].size()){
				result.erase(result.find(make_pair((*prev(bestEdge[it].end())).first,it)));
			}else{
				result.erase(result.find(make_pair(0,it)));
			}
			bestEdge[it].erase(bestEdge[it].find(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i])));
			upd(it,1,0,timer[it]-1,tin[it][i],timer[it]-1,df);
			upd(it,1,0,timer[it]-1,tout[it][i],timer[it]-1,-df);
			bestEdge[it].insert(make_pair(qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]),edgeRoot[it][i]));

			if(bestEdge[it].size() > 1){
				result.emplace((*prev(bestEdge[it].end())).first+(*prev(prev(bestEdge[it].end()))).first,it);
			}else if(bestEdge[it].size()){
				result.emplace((*prev(bestEdge[it].end())).first,it);
			}else{
				result.emplace(0,it);
			}
		}
		cost[i] = j;
		last = (*prev(result.end())).first;
		cout << (*prev(result.end())).first << "\n";
	}
}

Compilation message

diameter.cpp: In function 'void dfsSz(int, int)':
diameter.cpp:19:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'int fnCent(int, int, int)':
diameter.cpp:27:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsTour(int, int, int)':
diameter.cpp:35:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsEdgeRoot(int, int, int, int)':
diameter.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsCent(int, int)':
diameter.cpp:60:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp:69:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |  for(auto [v,w] : adj[cent]){
      |           ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30880 KB Output is correct
2 Correct 18 ms 30864 KB Output is correct
3 Correct 16 ms 30876 KB Output is correct
4 Correct 18 ms 30832 KB Output is correct
5 Correct 18 ms 30808 KB Output is correct
6 Correct 17 ms 30860 KB Output is correct
7 Correct 18 ms 30804 KB Output is correct
8 Correct 18 ms 30804 KB Output is correct
9 Correct 19 ms 30896 KB Output is correct
10 Correct 18 ms 30804 KB Output is correct
11 Correct 17 ms 30896 KB Output is correct
12 Correct 18 ms 30864 KB Output is correct
13 Correct 18 ms 30984 KB Output is correct
14 Correct 17 ms 30916 KB Output is correct
15 Correct 17 ms 30964 KB Output is correct
16 Correct 18 ms 30932 KB Output is correct
17 Correct 17 ms 30936 KB Output is correct
18 Correct 16 ms 30932 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30880 KB Output is correct
2 Correct 18 ms 30864 KB Output is correct
3 Correct 16 ms 30876 KB Output is correct
4 Correct 18 ms 30832 KB Output is correct
5 Correct 18 ms 30808 KB Output is correct
6 Correct 17 ms 30860 KB Output is correct
7 Correct 18 ms 30804 KB Output is correct
8 Correct 18 ms 30804 KB Output is correct
9 Correct 19 ms 30896 KB Output is correct
10 Correct 18 ms 30804 KB Output is correct
11 Correct 17 ms 30896 KB Output is correct
12 Correct 18 ms 30864 KB Output is correct
13 Correct 18 ms 30984 KB Output is correct
14 Correct 17 ms 30916 KB Output is correct
15 Correct 17 ms 30964 KB Output is correct
16 Correct 18 ms 30932 KB Output is correct
17 Correct 17 ms 30936 KB Output is correct
18 Correct 16 ms 30932 KB Output is correct
19 Correct 48 ms 32484 KB Output is correct
20 Correct 55 ms 32648 KB Output is correct
21 Correct 72 ms 32916 KB Output is correct
22 Correct 62 ms 33356 KB Output is correct
23 Correct 147 ms 39940 KB Output is correct
24 Correct 164 ms 42764 KB Output is correct
25 Correct 189 ms 44492 KB Output is correct
26 Correct 212 ms 46496 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30836 KB Output is correct
2 Correct 16 ms 30864 KB Output is correct
3 Correct 20 ms 30876 KB Output is correct
4 Correct 45 ms 31064 KB Output is correct
5 Correct 95 ms 31472 KB Output is correct
6 Correct 16 ms 30804 KB Output is correct
7 Correct 18 ms 31016 KB Output is correct
8 Correct 22 ms 31060 KB Output is correct
9 Correct 19 ms 31060 KB Output is correct
10 Correct 46 ms 31264 KB Output is correct
11 Correct 138 ms 31780 KB Output is correct
12 Correct 29 ms 33152 KB Output is correct
13 Correct 26 ms 33236 KB Output is correct
14 Correct 29 ms 33248 KB Output is correct
15 Correct 69 ms 33432 KB Output is correct
16 Correct 197 ms 33756 KB Output is correct
17 Correct 288 ms 78572 KB Output is correct
18 Correct 307 ms 78492 KB Output is correct
19 Correct 288 ms 78488 KB Output is correct
20 Correct 340 ms 78820 KB Output is correct
21 Correct 648 ms 79260 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33100 KB Output is correct
2 Correct 69 ms 33108 KB Output is correct
3 Correct 297 ms 33484 KB Output is correct
4 Correct 417 ms 33736 KB Output is correct
5 Correct 176 ms 60756 KB Output is correct
6 Correct 289 ms 60988 KB Output is correct
7 Correct 613 ms 61244 KB Output is correct
8 Correct 1045 ms 61428 KB Output is correct
9 Correct 1034 ms 210496 KB Output is correct
10 Correct 1140 ms 210440 KB Output is correct
11 Correct 1739 ms 210748 KB Output is correct
12 Correct 2556 ms 210920 KB Output is correct
13 Correct 2129 ms 414632 KB Output is correct
14 Correct 2376 ms 414560 KB Output is correct
15 Correct 3064 ms 414816 KB Output is correct
16 Correct 3919 ms 415144 KB Output is correct
17 Execution timed out 5060 ms 415064 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5077 ms 318788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30880 KB Output is correct
2 Correct 18 ms 30864 KB Output is correct
3 Correct 16 ms 30876 KB Output is correct
4 Correct 18 ms 30832 KB Output is correct
5 Correct 18 ms 30808 KB Output is correct
6 Correct 17 ms 30860 KB Output is correct
7 Correct 18 ms 30804 KB Output is correct
8 Correct 18 ms 30804 KB Output is correct
9 Correct 19 ms 30896 KB Output is correct
10 Correct 18 ms 30804 KB Output is correct
11 Correct 17 ms 30896 KB Output is correct
12 Correct 18 ms 30864 KB Output is correct
13 Correct 18 ms 30984 KB Output is correct
14 Correct 17 ms 30916 KB Output is correct
15 Correct 17 ms 30964 KB Output is correct
16 Correct 18 ms 30932 KB Output is correct
17 Correct 17 ms 30936 KB Output is correct
18 Correct 16 ms 30932 KB Output is correct
19 Correct 48 ms 32484 KB Output is correct
20 Correct 55 ms 32648 KB Output is correct
21 Correct 72 ms 32916 KB Output is correct
22 Correct 62 ms 33356 KB Output is correct
23 Correct 147 ms 39940 KB Output is correct
24 Correct 164 ms 42764 KB Output is correct
25 Correct 189 ms 44492 KB Output is correct
26 Correct 212 ms 46496 KB Output is correct
27 Correct 18 ms 30836 KB Output is correct
28 Correct 16 ms 30864 KB Output is correct
29 Correct 20 ms 30876 KB Output is correct
30 Correct 45 ms 31064 KB Output is correct
31 Correct 95 ms 31472 KB Output is correct
32 Correct 16 ms 30804 KB Output is correct
33 Correct 18 ms 31016 KB Output is correct
34 Correct 22 ms 31060 KB Output is correct
35 Correct 19 ms 31060 KB Output is correct
36 Correct 46 ms 31264 KB Output is correct
37 Correct 138 ms 31780 KB Output is correct
38 Correct 29 ms 33152 KB Output is correct
39 Correct 26 ms 33236 KB Output is correct
40 Correct 29 ms 33248 KB Output is correct
41 Correct 69 ms 33432 KB Output is correct
42 Correct 197 ms 33756 KB Output is correct
43 Correct 288 ms 78572 KB Output is correct
44 Correct 307 ms 78492 KB Output is correct
45 Correct 288 ms 78488 KB Output is correct
46 Correct 340 ms 78820 KB Output is correct
47 Correct 648 ms 79260 KB Output is correct
48 Correct 30 ms 33100 KB Output is correct
49 Correct 69 ms 33108 KB Output is correct
50 Correct 297 ms 33484 KB Output is correct
51 Correct 417 ms 33736 KB Output is correct
52 Correct 176 ms 60756 KB Output is correct
53 Correct 289 ms 60988 KB Output is correct
54 Correct 613 ms 61244 KB Output is correct
55 Correct 1045 ms 61428 KB Output is correct
56 Correct 1034 ms 210496 KB Output is correct
57 Correct 1140 ms 210440 KB Output is correct
58 Correct 1739 ms 210748 KB Output is correct
59 Correct 2556 ms 210920 KB Output is correct
60 Correct 2129 ms 414632 KB Output is correct
61 Correct 2376 ms 414560 KB Output is correct
62 Correct 3064 ms 414816 KB Output is correct
63 Correct 3919 ms 415144 KB Output is correct
64 Execution timed out 5060 ms 415064 KB Time limit exceeded
65 Halted 0 ms 0 KB -