oj.uz

Submission #618878

# Submission time Handle Problem Language Result Execution time Memory
618878 2022-08-02T08:09:26 Z sentheta Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 5000 ms 10248 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];
			u = u^v^1;

			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(w);

			int ans = *prev(s.end());
			if(s.size() >= 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 2 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 2 ms 2644 KB Output is correct
6 Correct 2 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 3 ms 2644 KB Output is correct
16 Correct 3 ms 2644 KB Output is correct
17 Correct 3 ms 2656 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 2 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 2 ms 2644 KB Output is correct
6 Correct 2 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 3 ms 2644 KB Output is correct
16 Correct 3 ms 2644 KB Output is correct
17 Correct 3 ms 2656 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 253 ms 2900 KB Output is correct
20 Correct 214 ms 2892 KB Output is correct
21 Correct 210 ms 2876 KB Output is correct
22 Correct 256 ms 2912 KB Output is correct
23 Correct 1691 ms 3052 KB Output is correct
24 Correct 1789 ms 3056 KB Output is correct
25 Correct 1779 ms 3084 KB Output is correct
26 Correct 2094 ms 3220 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 22 ms 2708 KB Output is correct
2 Correct 229 ms 3028 KB Output is correct
3 Correct 1099 ms 3884 KB Output is correct
4 Correct 2072 ms 4972 KB Output is correct
5 Correct 248 ms 3284 KB Output is correct
6 Correct 2513 ms 3492 KB Output is correct
7 Execution timed out 5055 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 5056 ms 10248 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 2 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 2 ms 2644 KB Output is correct
6 Correct 2 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 3 ms 2644 KB Output is correct
16 Correct 3 ms 2644 KB Output is correct
17 Correct 3 ms 2656 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 253 ms 2900 KB Output is correct
20 Correct 214 ms 2892 KB Output is correct
21 Correct 210 ms 2876 KB Output is correct
22 Correct 256 ms 2912 KB Output is correct
23 Correct 1691 ms 3052 KB Output is correct
24 Correct 1789 ms 3056 KB Output is correct
25 Correct 1779 ms 3084 KB Output is correct
26 Correct 2094 ms 3220 KB Output is correct
27 Runtime error 4 ms 5204 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -