oj.uz

Submission #619212

# Submission time Handle Problem Language Result Execution time Memory
619212 2022-08-02T10:32:40 Z HappyPacMan Dynamic Diameter (CEOI19_diameter) C++14
49 / 100
 5000 ms 488640 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));
	}
}
 
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]){
			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);
	}
	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: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:141:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |    auto [u,v] = bestEdge[i].top();
      |         ^
diameter.cpp:172:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  172 |     auto [u,v] = bestEdge[it].top();
      |          ^
diameter.cpp:190:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  190 |    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 20 ms 34756 KB Output is correct
3 Correct 21 ms 34704 KB Output is correct
4 Correct 20 ms 34780 KB Output is correct
5 Correct 20 ms 34772 KB Output is correct
6 Correct 19 ms 34744 KB Output is correct
7 Correct 19 ms 34852 KB Output is correct
8 Correct 20 ms 34752 KB Output is correct
9 Correct 20 ms 34752 KB Output is correct
10 Correct 20 ms 34784 KB Output is correct
11 Correct 22 ms 34820 KB Output is correct
12 Correct 22 ms 34816 KB Output is correct
13 Correct 21 ms 34900 KB Output is correct
14 Correct 20 ms 34900 KB Output is correct
15 Correct 20 ms 34900 KB Output is correct
16 Correct 21 ms 34900 KB Output is correct
17 Correct 20 ms 34940 KB Output is correct
18 Correct 22 ms 34900 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 34772 KB Output is correct
2 Correct 20 ms 34756 KB Output is correct
3 Correct 21 ms 34704 KB Output is correct
4 Correct 20 ms 34780 KB Output is correct
5 Correct 20 ms 34772 KB Output is correct
6 Correct 19 ms 34744 KB Output is correct
7 Correct 19 ms 34852 KB Output is correct
8 Correct 20 ms 34752 KB Output is correct
9 Correct 20 ms 34752 KB Output is correct
10 Correct 20 ms 34784 KB Output is correct
11 Correct 22 ms 34820 KB Output is correct
12 Correct 22 ms 34816 KB Output is correct
13 Correct 21 ms 34900 KB Output is correct
14 Correct 20 ms 34900 KB Output is correct
15 Correct 20 ms 34900 KB Output is correct
16 Correct 21 ms 34900 KB Output is correct
17 Correct 20 ms 34940 KB Output is correct
18 Correct 22 ms 34900 KB Output is correct
19 Correct 47 ms 36752 KB Output is correct
20 Correct 59 ms 36972 KB Output is correct
21 Correct 70 ms 37244 KB Output is correct
22 Correct 63 ms 37992 KB Output is correct
23 Correct 133 ms 44664 KB Output is correct
24 Correct 150 ms 47932 KB Output is correct
25 Correct 240 ms 50444 KB Output is correct
26 Correct 208 ms 52956 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 34772 KB Output is correct
2 Correct 25 ms 34772 KB Output is correct
3 Correct 20 ms 34840 KB Output is correct
4 Correct 42 ms 34964 KB Output is correct
5 Correct 111 ms 35508 KB Output is correct
6 Correct 19 ms 34820 KB Output is correct
7 Correct 24 ms 34972 KB Output is correct
8 Correct 23 ms 35028 KB Output is correct
9 Correct 20 ms 35028 KB Output is correct
10 Correct 38 ms 35452 KB Output is correct
11 Correct 122 ms 36664 KB Output is correct
12 Correct 33 ms 37072 KB Output is correct
13 Correct 26 ms 37084 KB Output is correct
14 Correct 29 ms 37116 KB Output is correct
15 Correct 53 ms 37516 KB Output is correct
16 Correct 163 ms 38256 KB Output is correct
17 Correct 196 ms 81940 KB Output is correct
18 Correct 160 ms 81976 KB Output is correct
19 Correct 189 ms 81888 KB Output is correct
20 Correct 216 ms 82176 KB Output is correct
21 Correct 403 ms 90376 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37076 KB Output is correct
2 Correct 72 ms 37632 KB Output is correct
3 Correct 225 ms 39532 KB Output is correct
4 Correct 494 ms 41860 KB Output is correct
5 Correct 151 ms 66888 KB Output is correct
6 Correct 233 ms 67828 KB Output is correct
7 Correct 517 ms 71380 KB Output is correct
8 Correct 991 ms 76012 KB Output is correct
9 Correct 786 ms 225836 KB Output is correct
10 Correct 932 ms 226676 KB Output is correct
11 Correct 1374 ms 229480 KB Output is correct
12 Correct 1985 ms 234060 KB Output is correct
13 Correct 1643 ms 443372 KB Output is correct
14 Correct 1771 ms 444544 KB Output is correct
15 Correct 2421 ms 449084 KB Output is correct
16 Correct 3049 ms 449692 KB Output is correct
17 Correct 4263 ms 488640 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5032 ms 360996 KB Time limit exceeded
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 20 ms 34756 KB Output is correct
3 Correct 21 ms 34704 KB Output is correct
4 Correct 20 ms 34780 KB Output is correct
5 Correct 20 ms 34772 KB Output is correct
6 Correct 19 ms 34744 KB Output is correct
7 Correct 19 ms 34852 KB Output is correct
8 Correct 20 ms 34752 KB Output is correct
9 Correct 20 ms 34752 KB Output is correct
10 Correct 20 ms 34784 KB Output is correct
11 Correct 22 ms 34820 KB Output is correct
12 Correct 22 ms 34816 KB Output is correct
13 Correct 21 ms 34900 KB Output is correct
14 Correct 20 ms 34900 KB Output is correct
15 Correct 20 ms 34900 KB Output is correct
16 Correct 21 ms 34900 KB Output is correct
17 Correct 20 ms 34940 KB Output is correct
18 Correct 22 ms 34900 KB Output is correct
19 Correct 47 ms 36752 KB Output is correct
20 Correct 59 ms 36972 KB Output is correct
21 Correct 70 ms 37244 KB Output is correct
22 Correct 63 ms 37992 KB Output is correct
23 Correct 133 ms 44664 KB Output is correct
24 Correct 150 ms 47932 KB Output is correct
25 Correct 240 ms 50444 KB Output is correct
26 Correct 208 ms 52956 KB Output is correct
27 Correct 19 ms 34772 KB Output is correct
28 Correct 25 ms 34772 KB Output is correct
29 Correct 20 ms 34840 KB Output is correct
30 Correct 42 ms 34964 KB Output is correct
31 Correct 111 ms 35508 KB Output is correct
32 Correct 19 ms 34820 KB Output is correct
33 Correct 24 ms 34972 KB Output is correct
34 Correct 23 ms 35028 KB Output is correct
35 Correct 20 ms 35028 KB Output is correct
36 Correct 38 ms 35452 KB Output is correct
37 Correct 122 ms 36664 KB Output is correct
38 Correct 33 ms 37072 KB Output is correct
39 Correct 26 ms 37084 KB Output is correct
40 Correct 29 ms 37116 KB Output is correct
41 Correct 53 ms 37516 KB Output is correct
42 Correct 163 ms 38256 KB Output is correct
43 Correct 196 ms 81940 KB Output is correct
44 Correct 160 ms 81976 KB Output is correct
45 Correct 189 ms 81888 KB Output is correct
46 Correct 216 ms 82176 KB Output is correct
47 Correct 403 ms 90376 KB Output is correct
48 Correct 39 ms 37076 KB Output is correct
49 Correct 72 ms 37632 KB Output is correct
50 Correct 225 ms 39532 KB Output is correct
51 Correct 494 ms 41860 KB Output is correct
52 Correct 151 ms 66888 KB Output is correct
53 Correct 233 ms 67828 KB Output is correct
54 Correct 517 ms 71380 KB Output is correct
55 Correct 991 ms 76012 KB Output is correct
56 Correct 786 ms 225836 KB Output is correct
57 Correct 932 ms 226676 KB Output is correct
58 Correct 1374 ms 229480 KB Output is correct
59 Correct 1985 ms 234060 KB Output is correct
60 Correct 1643 ms 443372 KB Output is correct
61 Correct 1771 ms 444544 KB Output is correct
62 Correct 2421 ms 449084 KB Output is correct
63 Correct 3049 ms 449692 KB Output is correct
64 Correct 4263 ms 488640 KB Output is correct
65 Execution timed out 5032 ms 360996 KB Time limit exceeded
66 Halted 0 ms 0 KB -