oj.uz

Submission #619147

# Submission time Handle Problem Language Result Execution time Memory
619147 2022-08-02T10:14:25 Z HappyPacMan Dynamic Diameter (CEOI19_diameter) C++14
18 / 100
 5000 ms 372488 KB 
#include <bits/stdc++.h>
#define int long long
#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));
	}
}
 
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.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(long long int, long long int)':
diameter.cpp:22:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'long long int fnCent(long long int, long long int, long long int)':
diameter.cpp:30:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsTour(long long int, long long int, long long int)':
diameter.cpp:38:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsEdgeRoot(long long int, long long int, long long int, long long int)':
diameter.cpp:48:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |  for(auto [v,w] : adj[u]){
      |           ^
diameter.cpp: In function 'void dfsCent(long long int, long long int)':
diameter.cpp:63:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp:72:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |  for(auto [v,w] : adj[cent]){
      |           ^
diameter.cpp: In function 'int32_t main()':
diameter.cpp:141:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |    auto [u,v] = bestEdge[i].top();
      |         ^
diameter.cpp:171:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  171 |     auto [u,v] = bestEdge[it].top();
      |          ^
diameter.cpp:189:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  189 |    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 22 ms 34772 KB Output is correct
3 Correct 19 ms 34772 KB Output is correct
4 Correct 19 ms 34776 KB Output is correct
5 Correct 19 ms 34772 KB Output is correct
6 Correct 22 ms 34672 KB Output is correct
7 Correct 20 ms 34820 KB Output is correct
8 Correct 19 ms 34772 KB Output is correct
9 Correct 21 ms 34844 KB Output is correct
10 Correct 19 ms 34772 KB Output is correct
11 Correct 20 ms 34772 KB Output is correct
12 Correct 20 ms 34780 KB Output is correct
13 Correct 20 ms 34916 KB Output is correct
14 Correct 21 ms 34900 KB Output is correct
15 Correct 20 ms 34816 KB Output is correct
16 Correct 21 ms 34840 KB Output is correct
17 Correct 21 ms 34948 KB Output is correct
18 Correct 26 ms 34900 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 22 ms 34772 KB Output is correct
3 Correct 19 ms 34772 KB Output is correct
4 Correct 19 ms 34776 KB Output is correct
5 Correct 19 ms 34772 KB Output is correct
6 Correct 22 ms 34672 KB Output is correct
7 Correct 20 ms 34820 KB Output is correct
8 Correct 19 ms 34772 KB Output is correct
9 Correct 21 ms 34844 KB Output is correct
10 Correct 19 ms 34772 KB Output is correct
11 Correct 20 ms 34772 KB Output is correct
12 Correct 20 ms 34780 KB Output is correct
13 Correct 20 ms 34916 KB Output is correct
14 Correct 21 ms 34900 KB Output is correct
15 Correct 20 ms 34816 KB Output is correct
16 Correct 21 ms 34840 KB Output is correct
17 Correct 21 ms 34948 KB Output is correct
18 Correct 26 ms 34900 KB Output is correct
19 Correct 49 ms 36852 KB Output is correct
20 Correct 51 ms 37076 KB Output is correct
21 Correct 57 ms 37304 KB Output is correct
22 Correct 64 ms 37996 KB Output is correct
23 Incorrect 101 ms 45244 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 21 ms 34752 KB Output is correct
2 Correct 20 ms 34772 KB Output is correct
3 Correct 21 ms 34796 KB Output is correct
4 Correct 37 ms 34988 KB Output is correct
5 Correct 104 ms 35484 KB Output is correct
6 Correct 20 ms 34772 KB Output is correct
7 Correct 21 ms 35028 KB Output is correct
8 Correct 20 ms 35020 KB Output is correct
9 Correct 22 ms 35028 KB Output is correct
10 Correct 44 ms 35360 KB Output is correct
11 Correct 121 ms 36416 KB Output is correct
12 Correct 26 ms 37088 KB Output is correct
13 Correct 26 ms 37072 KB Output is correct
14 Correct 28 ms 37176 KB Output is correct
15 Correct 50 ms 37568 KB Output is correct
16 Correct 147 ms 38344 KB Output is correct
17 Correct 150 ms 83808 KB Output is correct
18 Correct 155 ms 83884 KB Output is correct
19 Correct 159 ms 83920 KB Output is correct
20 Correct 218 ms 84236 KB Output is correct
21 Correct 397 ms 92300 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 37168 KB Output is correct
2 Correct 64 ms 37824 KB Output is correct
3 Correct 223 ms 39464 KB Output is correct
4 Incorrect 587 ms 46580 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 5103 ms 372488 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 22 ms 34772 KB Output is correct
3 Correct 19 ms 34772 KB Output is correct
4 Correct 19 ms 34776 KB Output is correct
5 Correct 19 ms 34772 KB Output is correct
6 Correct 22 ms 34672 KB Output is correct
7 Correct 20 ms 34820 KB Output is correct
8 Correct 19 ms 34772 KB Output is correct
9 Correct 21 ms 34844 KB Output is correct
10 Correct 19 ms 34772 KB Output is correct
11 Correct 20 ms 34772 KB Output is correct
12 Correct 20 ms 34780 KB Output is correct
13 Correct 20 ms 34916 KB Output is correct
14 Correct 21 ms 34900 KB Output is correct
15 Correct 20 ms 34816 KB Output is correct
16 Correct 21 ms 34840 KB Output is correct
17 Correct 21 ms 34948 KB Output is correct
18 Correct 26 ms 34900 KB Output is correct
19 Correct 49 ms 36852 KB Output is correct
20 Correct 51 ms 37076 KB Output is correct
21 Correct 57 ms 37304 KB Output is correct
22 Correct 64 ms 37996 KB Output is correct
23 Incorrect 101 ms 45244 KB Output isn't correct
24 Halted 0 ms 0 KB -