oj.uz

Submission #619251

# Submission time Handle Problem Language Result Execution time Memory
619251 2022-08-02T10:45:01 Z HappyPacMan Dynamic Diameter (CEOI19_diameter) C++14
11 / 100
 2538 ms 691156 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];
vector<int> partOf[maxn];
vector<ll> seg[maxn],lazy[maxn];
bool isCent[maxn];
int subSz[maxn],timer[maxn];
unordered_map<int,int> tin[maxn],tout[maxn],edgeRoot[maxn];
unordered_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;
	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);
 	
 	auto now = clock();
	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);
		cost[i] = w;
	}
	dfsCent(0,-1);
	for(int i=1;i<n;i++){
		for(int it : partOf[i]){
			int z = edgeRoot[it][i];
			upd(it,1,0,timer[it]-1,tin[it][i],tout[it][i]-1,cost[i]);
			costEdge[it][z] = qry(it,1,0,timer[it]-1,tin[it][z],tout[it][z]);
			bestEdge[it].emplace(costEdge[it][z],z);
		}
	}
	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);
	}
	assert(clock()-now <= 3000);
	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]){
			int z = edgeRoot[it][i];
			upd(it,1,0,timer[it]-1,tin[it][i],tout[it][i]-1,df);
			costEdge[it][z] = qry(it,1,0,timer[it]-1,tin[it][z],tout[it][z]);
			bestEdge[it].emplace(costEdge[it][z],z);
			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:59:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp:68:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp: In function 'int32_t main()':
diameter.cpp:138:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |    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 21 ms 34772 KB Output is correct
2 Correct 21 ms 34760 KB Output is correct
3 Correct 21 ms 34796 KB Output is correct
4 Correct 28 ms 34780 KB Output is correct
5 Correct 28 ms 34772 KB Output is correct
6 Correct 20 ms 34800 KB Output is correct
7 Correct 22 ms 34772 KB Output is correct
8 Correct 22 ms 34856 KB Output is correct
9 Correct 20 ms 34808 KB Output is correct
10 Correct 23 ms 34796 KB Output is correct
11 Correct 21 ms 34784 KB Output is correct
12 Correct 20 ms 34772 KB Output is correct
13 Correct 24 ms 34972 KB Output is correct
14 Correct 22 ms 34900 KB Output is correct
15 Correct 22 ms 34844 KB Output is correct
16 Correct 23 ms 34904 KB Output is correct
17 Correct 23 ms 34900 KB Output is correct
18 Correct 21 ms 34908 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 34772 KB Output is correct
2 Correct 21 ms 34760 KB Output is correct
3 Correct 21 ms 34796 KB Output is correct
4 Correct 28 ms 34780 KB Output is correct
5 Correct 28 ms 34772 KB Output is correct
6 Correct 20 ms 34800 KB Output is correct
7 Correct 22 ms 34772 KB Output is correct
8 Correct 22 ms 34856 KB Output is correct
9 Correct 20 ms 34808 KB Output is correct
10 Correct 23 ms 34796 KB Output is correct
11 Correct 21 ms 34784 KB Output is correct
12 Correct 20 ms 34772 KB Output is correct
13 Correct 24 ms 34972 KB Output is correct
14 Correct 22 ms 34900 KB Output is correct
15 Correct 22 ms 34844 KB Output is correct
16 Correct 23 ms 34904 KB Output is correct
17 Correct 23 ms 34900 KB Output is correct
18 Correct 21 ms 34908 KB Output is correct
19 Runtime error 55 ms 73732 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34796 KB Output is correct
2 Correct 20 ms 34696 KB Output is correct
3 Correct 22 ms 34772 KB Output is correct
4 Correct 36 ms 34888 KB Output is correct
5 Correct 125 ms 35436 KB Output is correct
6 Correct 20 ms 34772 KB Output is correct
7 Correct 19 ms 34920 KB Output is correct
8 Correct 22 ms 34932 KB Output is correct
9 Correct 22 ms 35028 KB Output is correct
10 Correct 41 ms 35412 KB Output is correct
11 Correct 132 ms 36492 KB Output is correct
12 Runtime error 56 ms 74928 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 60 ms 74868 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2538 ms 691156 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 34772 KB Output is correct
2 Correct 21 ms 34760 KB Output is correct
3 Correct 21 ms 34796 KB Output is correct
4 Correct 28 ms 34780 KB Output is correct
5 Correct 28 ms 34772 KB Output is correct
6 Correct 20 ms 34800 KB Output is correct
7 Correct 22 ms 34772 KB Output is correct
8 Correct 22 ms 34856 KB Output is correct
9 Correct 20 ms 34808 KB Output is correct
10 Correct 23 ms 34796 KB Output is correct
11 Correct 21 ms 34784 KB Output is correct
12 Correct 20 ms 34772 KB Output is correct
13 Correct 24 ms 34972 KB Output is correct
14 Correct 22 ms 34900 KB Output is correct
15 Correct 22 ms 34844 KB Output is correct
16 Correct 23 ms 34904 KB Output is correct
17 Correct 23 ms 34900 KB Output is correct
18 Correct 21 ms 34908 KB Output is correct
19 Runtime error 55 ms 73732 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -