oj.uz

Submission #619145

# Submission time Handle Problem Language Result Execution time Memory
619145 2022-08-02T10:13:11 Z HappyPacMan Dynamic Diameter (CEOI19_diameter) C++14
18 / 100
 5000 ms 362796 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];
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;
	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]){
			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.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 'int 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 34772 KB Output is correct
2 Correct 20 ms 34736 KB Output is correct
3 Correct 20 ms 34804 KB Output is correct
4 Correct 20 ms 34796 KB Output is correct
5 Correct 21 ms 34756 KB Output is correct
6 Correct 22 ms 34840 KB Output is correct
7 Correct 21 ms 34848 KB Output is correct
8 Correct 20 ms 34772 KB Output is correct
9 Correct 19 ms 34772 KB Output is correct
10 Correct 22 ms 34772 KB Output is correct
11 Correct 24 ms 34920 KB Output is correct
12 Correct 20 ms 34772 KB Output is correct
13 Correct 20 ms 34900 KB Output is correct
14 Correct 19 ms 34888 KB Output is correct
15 Correct 20 ms 34908 KB Output is correct
16 Correct 20 ms 34924 KB Output is correct
17 Correct 20 ms 34832 KB Output is correct
18 Correct 21 ms 34872 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 34772 KB Output is correct
2 Correct 20 ms 34736 KB Output is correct
3 Correct 20 ms 34804 KB Output is correct
4 Correct 20 ms 34796 KB Output is correct
5 Correct 21 ms 34756 KB Output is correct
6 Correct 22 ms 34840 KB Output is correct
7 Correct 21 ms 34848 KB Output is correct
8 Correct 20 ms 34772 KB Output is correct
9 Correct 19 ms 34772 KB Output is correct
10 Correct 22 ms 34772 KB Output is correct
11 Correct 24 ms 34920 KB Output is correct
12 Correct 20 ms 34772 KB Output is correct
13 Correct 20 ms 34900 KB Output is correct
14 Correct 19 ms 34888 KB Output is correct
15 Correct 20 ms 34908 KB Output is correct
16 Correct 20 ms 34924 KB Output is correct
17 Correct 20 ms 34832 KB Output is correct
18 Correct 21 ms 34872 KB Output is correct
19 Correct 49 ms 36796 KB Output is correct
20 Correct 51 ms 37012 KB Output is correct
21 Correct 60 ms 37316 KB Output is correct
22 Correct 64 ms 37980 KB Output is correct
23 Incorrect 116 ms 44896 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34692 KB Output is correct
2 Correct 24 ms 34784 KB Output is correct
3 Correct 26 ms 34892 KB Output is correct
4 Correct 38 ms 34892 KB Output is correct
5 Correct 108 ms 35536 KB Output is correct
6 Correct 19 ms 34748 KB Output is correct
7 Correct 22 ms 34924 KB Output is correct
8 Correct 22 ms 35028 KB Output is correct
9 Correct 25 ms 35028 KB Output is correct
10 Correct 45 ms 35396 KB Output is correct
11 Correct 128 ms 36416 KB Output is correct
12 Correct 26 ms 37072 KB Output is correct
13 Correct 32 ms 37000 KB Output is correct
14 Correct 30 ms 37112 KB Output is correct
15 Correct 55 ms 37460 KB Output is correct
16 Correct 147 ms 38204 KB Output is correct
17 Correct 161 ms 81884 KB Output is correct
18 Correct 154 ms 81932 KB Output is correct
19 Correct 160 ms 81944 KB Output is correct
20 Correct 200 ms 82168 KB Output is correct
21 Correct 389 ms 90316 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 37192 KB Output is correct
2 Correct 69 ms 37724 KB Output is correct
3 Correct 225 ms 39820 KB Output is correct
4 Incorrect 619 ms 47464 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5095 ms 362796 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 34772 KB Output is correct
2 Correct 20 ms 34736 KB Output is correct
3 Correct 20 ms 34804 KB Output is correct
4 Correct 20 ms 34796 KB Output is correct
5 Correct 21 ms 34756 KB Output is correct
6 Correct 22 ms 34840 KB Output is correct
7 Correct 21 ms 34848 KB Output is correct
8 Correct 20 ms 34772 KB Output is correct
9 Correct 19 ms 34772 KB Output is correct
10 Correct 22 ms 34772 KB Output is correct
11 Correct 24 ms 34920 KB Output is correct
12 Correct 20 ms 34772 KB Output is correct
13 Correct 20 ms 34900 KB Output is correct
14 Correct 19 ms 34888 KB Output is correct
15 Correct 20 ms 34908 KB Output is correct
16 Correct 20 ms 34924 KB Output is correct
17 Correct 20 ms 34832 KB Output is correct
18 Correct 21 ms 34872 KB Output is correct
19 Correct 49 ms 36796 KB Output is correct
20 Correct 51 ms 37012 KB Output is correct
21 Correct 60 ms 37316 KB Output is correct
22 Correct 64 ms 37980 KB Output is correct
23 Incorrect 116 ms 44896 KB Output isn't correct
24 Halted 0 ms 0 KB -