oj.uz

Submission #275951

# Submission time Handle Problem Language Result Execution time Memory
275951 2020-08-20T08:34:01 Z theStaticMind Dynamic Diameter (CEOI19_diameter) C++14
36 / 100
 5000 ms 35152 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
int n;

vector<ii> adj[100005];
vector<ii> edge;
int anc[20][100005];
int depth[100005];

multiset<int> diameter;
multiset<int> data[100005];
map<int, int> ptr;

int getedge(int x, int y){
	return lower_bound(all(adj[x]), ii{y, -1}) - adj[x].begin();
}

int getdia(int x){
	if(data[x].empty()) return 0;
	if(data[x].size() == 1) return *data[x].rbegin();
	return *data[x].rbegin() + *++data[x].rbegin();
}
int getmax(int x){
	if(data[x].empty()) return 0;
	return *data[x].rbegin();	
}

void update(int x, int y){
	diameter.erase(diameter.find(getdia(x)));
	data[x].erase(data[x].lower_bound(ptr[y]));
	ptr[y] = getmax(y) + adj[x][getedge(x, y)].second;
	data[x].insert(ptr[y]);
	diameter.insert(getdia(x));
}

void init(int x, int pre){

	for(auto p : adj[x]){
		int y = p.first;
		if(y == pre) continue;
		
		anc[0][y] = x;
		depth[y] = depth[x] + 1;

		init(y, x);

		data[x].insert(getmax(y) + p.second);
		ptr[y] = getmax(y) + p.second;

	}

	diameter.insert(getdia(x));
}


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int q, W;
	cin >> n >> q >> W;

	for(int i = 0; i < n - 1; i++){
		int x, y, z;
		cin >> x >> y >> z;
		adj[x].pb({y, z});
		adj[y].pb({x, z});

		edge.pb({x, y});
	}

	for(int i = 1; i <= n; i++){
		sort(all(adj[i]));
	}

	init(1, 0);

	int last = 0;

	while(q--){
		ii p;
		cin >> p.first >> p.second;
		p.first = (p.first + last) % (n - 1);
		p.second = (p.second + last) % W;
		int x = edge[p.first].first;
		int y = edge[p.first].second;
		int z = p.second;

		adj[x][getedge(x, y)].second = z;
		adj[y][getedge(y, x)].second = z;

		if(depth[x] > depth[y]) swap(x, y);

		while(x){
			update(x, y);
			y = x;
			x = anc[0][x];
		}

		last = *diameter.rbegin();
		cout << last << "\n";
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7552 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 6 ms 7424 KB Output is correct
12 Correct 6 ms 7424 KB Output is correct
13 Correct 7 ms 7424 KB Output is correct
14 Correct 5 ms 7424 KB Output is correct
15 Correct 5 ms 7424 KB Output is correct
16 Correct 6 ms 7372 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7552 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 6 ms 7424 KB Output is correct
12 Correct 6 ms 7424 KB Output is correct
13 Correct 7 ms 7424 KB Output is correct
14 Correct 5 ms 7424 KB Output is correct
15 Correct 5 ms 7424 KB Output is correct
16 Correct 6 ms 7372 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 39 ms 7680 KB Output is correct
20 Correct 72 ms 7680 KB Output is correct
21 Correct 270 ms 7800 KB Output is correct
22 Correct 672 ms 8012 KB Output is correct
23 Correct 60 ms 8576 KB Output is correct
24 Correct 308 ms 8700 KB Output is correct
25 Correct 1088 ms 8824 KB Output is correct
26 Execution timed out 5040 ms 9336 KB Time limit exceeded

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 17 ms 7424 KB Output is correct
5 Correct 66 ms 7800 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 5 ms 7552 KB Output is correct
8 Correct 6 ms 7552 KB Output is correct
9 Correct 8 ms 7552 KB Output is correct
10 Correct 24 ms 7552 KB Output is correct
11 Correct 108 ms 7964 KB Output is correct
12 Correct 10 ms 8576 KB Output is correct
13 Correct 10 ms 8576 KB Output is correct
14 Correct 13 ms 8576 KB Output is correct
15 Correct 63 ms 8696 KB Output is correct
16 Correct 179 ms 9284 KB Output is correct
17 Correct 178 ms 30952 KB Output is correct
18 Correct 211 ms 30932 KB Output is correct
19 Correct 188 ms 30932 KB Output is correct
20 Correct 241 ms 31052 KB Output is correct
21 Correct 702 ms 31444 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7680 KB Output is correct
2 Correct 30 ms 7680 KB Output is correct
3 Correct 130 ms 7928 KB Output is correct
4 Correct 275 ms 8164 KB Output is correct
5 Correct 20 ms 9852 KB Output is correct
6 Correct 59 ms 9852 KB Output is correct
7 Correct 230 ms 10228 KB Output is correct
8 Correct 477 ms 11508 KB Output is correct
9 Correct 86 ms 20332 KB Output is correct
10 Correct 146 ms 20716 KB Output is correct
11 Correct 456 ms 21356 KB Output is correct
12 Correct 986 ms 22108 KB Output is correct
13 Correct 177 ms 33252 KB Output is correct
14 Correct 264 ms 33480 KB Output is correct
15 Correct 651 ms 34136 KB Output is correct
16 Correct 1079 ms 35152 KB Output is correct
17 Correct 3279 ms 34776 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7552 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 6 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 6 ms 7424 KB Output is correct
12 Correct 6 ms 7424 KB Output is correct
13 Correct 7 ms 7424 KB Output is correct
14 Correct 5 ms 7424 KB Output is correct
15 Correct 5 ms 7424 KB Output is correct
16 Correct 6 ms 7372 KB Output is correct
17 Correct 6 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 39 ms 7680 KB Output is correct
20 Correct 72 ms 7680 KB Output is correct
21 Correct 270 ms 7800 KB Output is correct
22 Correct 672 ms 8012 KB Output is correct
23 Correct 60 ms 8576 KB Output is correct
24 Correct 308 ms 8700 KB Output is correct
25 Correct 1088 ms 8824 KB Output is correct
26 Execution timed out 5040 ms 9336 KB Time limit exceeded