oj.uz

Submission #619200

# Submission time Handle Problem Language Result Execution time Memory
619200 2022-08-02T10:30:24 Z HappyPacMan Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 5000 ms 460872 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];
map<int,int> tin[maxn],tout[maxn],edgeRoot[maxn];
map<int,ll> costEdge[maxn];
ll tempResult[maxn];
priority_queue<pair<ll,int> > 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));
	}
}
 
int32_t 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]){
			upd(it,1,0,timer[it]-1,tin[it][i],tout[it][i]-1,cost[i]);
			costEdge[it][edgeRoot[it][i]] = qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]);
			bestEdge[it].emplace(costEdge[it][edgeRoot[it][i]],edgeRoot[it][i]);
		}
	}
	for(int i=0;i<n;i++){
		vector<pair<ll,int> > best;
		while(!bestEdge[i].empty() && best.size() < 2){
			auto [u,v] = bestEdge[i].top();
			bestEdge[i].pop();
			if(costEdge[i][v] == u && (best.empty() || best.back() != make_pair(u,v))){
				best.emplace_back(u,v);
			}
		}
		ll sum = 0;
		for(auto it : best){
			sum += it.first;
		}
		for(auto it : best){
			bestEdge[i].emplace(it);
		}
		tempResult[i] = sum;
		result.emplace(tempResult[i],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]){
			upd(it,1,0,timer[it]-1,tin[it][i],tout[it][i]-1,df);
			costEdge[it][edgeRoot[it][i]] = qry(it,1,0,timer[it]-1,tin[it][edgeRoot[it][i]],tout[it][edgeRoot[it][i]]);
			bestEdge[it].emplace(costEdge[it][edgeRoot[it][i]],edgeRoot[it][i]);
			vector<pair<ll,int> > best;
			while(!bestEdge[it].empty() && best.size() < 2){
				auto [u,v] = bestEdge[it].top();
				bestEdge[it].pop();
				if(costEdge[it][v] == u && (best.empty() || best.back() != make_pair(u,v))){
					best.emplace_back(u,v);
				}
			}
			ll sum = 0;
			for(auto it2 : best){
				sum += it2.first;
			}
			for(auto it2 : best){
				bestEdge[it].emplace(it2);
			}
			tempResult[it] = sum;
			result.emplace(tempResult[it],it);
		}
		cost[i] = j;
		while(true){
			auto [u,v] = result.top();
			if(tempResult[v] == u){
				break;
			}
			result.pop();
		}
		last = result.top().first;
		cout << result.top().first << "\n";
	}
}

Compilation message

diameter.cpp: In function 'void dfsSz(int, int)':
diameter.cpp:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'int fnCent(int, int, int)':
diameter.cpp:29:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsTour(int, int, int)':
diameter.cpp:37:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsEdgeRoot(int, int, int, int)':
diameter.cpp:47:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsCent(int, int)':
diameter.cpp:62:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp:71:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp: In function 'int32_t main()':
diameter.cpp:140:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |    auto [u,v] = bestEdge[i].top();
      |         ^
diameter.cpp:170:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  170 |     auto [u,v] = bestEdge[it].top();
      |          ^
diameter.cpp:188:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  188 |    auto [u,v] = result.top();
      |         ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31572 KB Output is correct
2 Correct 18 ms 31580 KB Output is correct
3 Correct 19 ms 31616 KB Output is correct
4 Correct 19 ms 31612 KB Output is correct
5 Correct 21 ms 31544 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 19 ms 31700 KB Output is correct
8 Correct 19 ms 31700 KB Output is correct
9 Correct 21 ms 31704 KB Output is correct
10 Correct 21 ms 31716 KB Output is correct
11 Correct 17 ms 31700 KB Output is correct
12 Correct 19 ms 31700 KB Output is correct
13 Correct 18 ms 31700 KB Output is correct
14 Correct 18 ms 31700 KB Output is correct
15 Correct 18 ms 31700 KB Output is correct
16 Correct 20 ms 31700 KB Output is correct
17 Correct 18 ms 31700 KB Output is correct
18 Correct 21 ms 31828 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31572 KB Output is correct
2 Correct 18 ms 31580 KB Output is correct
3 Correct 19 ms 31616 KB Output is correct
4 Correct 19 ms 31612 KB Output is correct
5 Correct 21 ms 31544 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 19 ms 31700 KB Output is correct
8 Correct 19 ms 31700 KB Output is correct
9 Correct 21 ms 31704 KB Output is correct
10 Correct 21 ms 31716 KB Output is correct
11 Correct 17 ms 31700 KB Output is correct
12 Correct 19 ms 31700 KB Output is correct
13 Correct 18 ms 31700 KB Output is correct
14 Correct 18 ms 31700 KB Output is correct
15 Correct 18 ms 31700 KB Output is correct
16 Correct 20 ms 31700 KB Output is correct
17 Correct 18 ms 31700 KB Output is correct
18 Correct 21 ms 31828 KB Output is correct
19 Correct 61 ms 33612 KB Output is correct
20 Correct 75 ms 33896 KB Output is correct
21 Correct 74 ms 34244 KB Output is correct
22 Correct 83 ms 34956 KB Output is correct
23 Correct 151 ms 41640 KB Output is correct
24 Correct 217 ms 45000 KB Output is correct
25 Correct 254 ms 47352 KB Output is correct
26 Correct 278 ms 49696 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 19 ms 31608 KB Output is correct
3 Correct 25 ms 31596 KB Output is correct
4 Correct 36 ms 31916 KB Output is correct
5 Correct 120 ms 33012 KB Output is correct
6 Correct 22 ms 31628 KB Output is correct
7 Correct 18 ms 31908 KB Output is correct
8 Correct 23 ms 31836 KB Output is correct
9 Correct 25 ms 31936 KB Output is correct
10 Correct 64 ms 32432 KB Output is correct
11 Correct 210 ms 33600 KB Output is correct
12 Correct 28 ms 34212 KB Output is correct
13 Correct 31 ms 34132 KB Output is correct
14 Correct 32 ms 34172 KB Output is correct
15 Correct 79 ms 34516 KB Output is correct
16 Correct 276 ms 35324 KB Output is correct
17 Correct 306 ms 81204 KB Output is correct
18 Correct 313 ms 81060 KB Output is correct
19 Correct 318 ms 81184 KB Output is correct
20 Correct 434 ms 81384 KB Output is correct
21 Correct 876 ms 85636 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34016 KB Output is correct
2 Correct 86 ms 34508 KB Output is correct
3 Correct 328 ms 36164 KB Output is correct
4 Correct 613 ms 38560 KB Output is correct
5 Correct 214 ms 64240 KB Output is correct
6 Correct 360 ms 65108 KB Output is correct
7 Correct 1010 ms 68796 KB Output is correct
8 Correct 1815 ms 73916 KB Output is correct
9 Correct 1302 ms 228764 KB Output is correct
10 Correct 1389 ms 229564 KB Output is correct
11 Correct 2484 ms 232216 KB Output is correct
12 Correct 4560 ms 237024 KB Output is correct
13 Correct 2870 ms 453664 KB Output is correct
14 Correct 3100 ms 455640 KB Output is correct
15 Correct 4970 ms 460872 KB Output is correct
16 Execution timed out 5111 ms 460664 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31572 KB Output is correct
2 Correct 18 ms 31580 KB Output is correct
3 Correct 19 ms 31616 KB Output is correct
4 Correct 19 ms 31612 KB Output is correct
5 Correct 21 ms 31544 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 19 ms 31700 KB Output is correct
8 Correct 19 ms 31700 KB Output is correct
9 Correct 21 ms 31704 KB Output is correct
10 Correct 21 ms 31716 KB Output is correct
11 Correct 17 ms 31700 KB Output is correct
12 Correct 19 ms 31700 KB Output is correct
13 Correct 18 ms 31700 KB Output is correct
14 Correct 18 ms 31700 KB Output is correct
15 Correct 18 ms 31700 KB Output is correct
16 Correct 20 ms 31700 KB Output is correct
17 Correct 18 ms 31700 KB Output is correct
18 Correct 21 ms 31828 KB Output is correct
19 Correct 61 ms 33612 KB Output is correct
20 Correct 75 ms 33896 KB Output is correct
21 Correct 74 ms 34244 KB Output is correct
22 Correct 83 ms 34956 KB Output is correct
23 Correct 151 ms 41640 KB Output is correct
24 Correct 217 ms 45000 KB Output is correct
25 Correct 254 ms 47352 KB Output is correct
26 Correct 278 ms 49696 KB Output is correct
27 Correct 17 ms 31572 KB Output is correct
28 Correct 19 ms 31608 KB Output is correct
29 Correct 25 ms 31596 KB Output is correct
30 Correct 36 ms 31916 KB Output is correct
31 Correct 120 ms 33012 KB Output is correct
32 Correct 22 ms 31628 KB Output is correct
33 Correct 18 ms 31908 KB Output is correct
34 Correct 23 ms 31836 KB Output is correct
35 Correct 25 ms 31936 KB Output is correct
36 Correct 64 ms 32432 KB Output is correct
37 Correct 210 ms 33600 KB Output is correct
38 Correct 28 ms 34212 KB Output is correct
39 Correct 31 ms 34132 KB Output is correct
40 Correct 32 ms 34172 KB Output is correct
41 Correct 79 ms 34516 KB Output is correct
42 Correct 276 ms 35324 KB Output is correct
43 Correct 306 ms 81204 KB Output is correct
44 Correct 313 ms 81060 KB Output is correct
45 Correct 318 ms 81184 KB Output is correct
46 Correct 434 ms 81384 KB Output is correct
47 Correct 876 ms 85636 KB Output is correct
48 Correct 37 ms 34016 KB Output is correct
49 Correct 86 ms 34508 KB Output is correct
50 Correct 328 ms 36164 KB Output is correct
51 Correct 613 ms 38560 KB Output is correct
52 Correct 214 ms 64240 KB Output is correct
53 Correct 360 ms 65108 KB Output is correct
54 Correct 1010 ms 68796 KB Output is correct
55 Correct 1815 ms 73916 KB Output is correct
56 Correct 1302 ms 228764 KB Output is correct
57 Correct 1389 ms 229564 KB Output is correct
58 Correct 2484 ms 232216 KB Output is correct
59 Correct 4560 ms 237024 KB Output is correct
60 Correct 2870 ms 453664 KB Output is correct
61 Correct 3100 ms 455640 KB Output is correct
62 Correct 4970 ms 460872 KB Output is correct
63 Execution timed out 5111 ms 460664 KB Time limit exceeded
64 Halted 0 ms 0 KB -