oj.uz

Submission #618890

# Submission time Handle Problem Language Result Execution time Memory
618890 2022-08-02T08:13:40 Z sentheta Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 5000 ms 10244 KB 
#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

#define V vector
#define Int long long
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define all(x) (x).begin(), (x).end()

#define int long long
#define pii pair<int,int>

const int N = 1e5+5;
int n, q, wlim;
V<array<int,3>> edges;
V<pair<int,int>> queries;

struct Sub1{
	V<int> adj[N];
	int mxdist = 0, mxnode = -1;
	void dfs(int x,int par=-1,int dist=0){
		if(dist >= mxdist){
			mxdist = dist;
			mxnode = x;
		}

		for(int id : adj[x]){
			int y = edges[id][0]^edges[id][1]^x;
			int w = edges[id][2];
			if(y==par) continue;

			dfs(y,x, dist+w);
		}
	}
	void run(){
		rep(i,0,n-1){
			auto[u,v,w] = edges[i];
			adj[u].push_back(i);
			adj[v].push_back(i);
		}

		int last = 0;
		for(auto[i,w] : queries){
			i = (i+last)%(n-1);
			w = (w+last)%wlim;
			edges[i][2] = w;

			mxdist = 0;
			dfs(1);
			dfs(mxnode);

			cout << mxdist << nl;
			last = mxdist;
		}
	}
};

struct Sub3{
	int arr[N];
	multiset<int> s;
	void run(){
		rep(i,0,n-1){
			auto[u,v,w] = edges[i];
			if(u==1) swap(u,v);

			arr[u] = w;
			s.insert(w);
		}

		int last = 0;
		for(auto[i,w] : queries){
			i = (i+last)%(n-1);
			w = (w+last)%wlim;

			s.erase(s.find(arr[i]));
			arr[i] = w;
			s.insert(arr[i]);

			int ans = *prev(s.end());
			if(n > 2){
				ans += *prev(prev(s.end()));
			}

			cout << ans << nl;
			last = ans;
		}
	}
};

signed main(){

	cin >> n >> q >> wlim;
	
	rep(i,0,n-1){
		int u, v, w;
		cin >> u >> v >> w;

		edges.push_back({u,v,w});
	}
	rep(i,0,q){
		int idx, w;
		cin >> idx >> w;

		queries.push_back({idx,w});
	}

	bool sub3 = 1;
	rep(i,0,n-1){
		auto[u,v,w] = edges[i];
		sub3 &= (u==1 || v==1);
	}
	if(sub3){
		Sub3 sub; sub.run(); return 0;
	}

	Sub1 sub; sub.run(); return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 180 ms 2892 KB Output is correct
20 Correct 195 ms 2872 KB Output is correct
21 Correct 198 ms 2900 KB Output is correct
22 Correct 231 ms 3036 KB Output is correct
23 Correct 1400 ms 3056 KB Output is correct
24 Correct 1592 ms 3156 KB Output is correct
25 Correct 1549 ms 3212 KB Output is correct
26 Correct 1760 ms 3308 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2728 KB Output is correct
2 Correct 195 ms 3028 KB Output is correct
3 Correct 969 ms 4036 KB Output is correct
4 Correct 1945 ms 5116 KB Output is correct
5 Correct 232 ms 3284 KB Output is correct
6 Correct 2310 ms 3620 KB Output is correct
7 Execution timed out 5031 ms 4208 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 180 ms 2892 KB Output is correct
20 Correct 195 ms 2872 KB Output is correct
21 Correct 198 ms 2900 KB Output is correct
22 Correct 231 ms 3036 KB Output is correct
23 Correct 1400 ms 3056 KB Output is correct
24 Correct 1592 ms 3156 KB Output is correct
25 Correct 1549 ms 3212 KB Output is correct
26 Correct 1760 ms 3308 KB Output is correct
27 Runtime error 4 ms 5204 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -