oj.uz

Submission #943951

# Submission time Handle Problem Language Result Execution time Memory
943951 2024-03-12T05:21:29 Z vjudge1 Dynamic Diameter (CEOI19_diameter) C++17
18 / 100
 5000 ms 29956 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)v.size()
 
const int INF = 1e18;
const int mod = 998244353;
const int N = 1e5+5;
int p[N], d[N], dp[N], _res[N];
map<pair<int,int>,int> w;
vector<int> g[N], order;
multiset<int> ans;

void dfs(int v){
	for(auto to : g[v]){
		if(to != p[v]){
			p[to] = v;
			d[to] = d[v] + 1;
			dfs(to);
		}
	}
	order.pb(v);
}

void solve(){
	int n, q, wmax;
	cin >> n >> q >> wmax;
	vector<pair<int,int> > edges(n + 1);
	for(int i = 0; i < n - 1; i++){
		int u, v, wi;
		cin >> u >> v >> wi;
		g[u].pb(v);
		g[v].pb(u);
		w[{u, v}] = wi;
		w[{v, u}] = wi;
		edges[i] = {u, v};
	}
	dfs(1);
	for(int v : order){
		for(auto to : g[v]){
			if(to != p[v]){
				dp[v] = max(dp[v], dp[to] + w[{v, to}]);
				_res[v] += dp[to] + w[{v, to}];
			}
		}
		
		ans.insert(_res[v]);
	}
	int last = 0;
	while(q--){
		int ind, val;
		cin >> ind >> val;
		ind = (ind + last) % (n - 1);
		val = (val + last) % wmax;
		auto [u, v] = edges[ind];
		if(d[u] < d[v]) swap(u, v);
		w[{u, v}] = val;
		w[{v, u}] = val;
		while(v){
			int res = 0;
			dp[v] = 0;
			for(auto to : g[v]){
				if(to != p[v]){
					dp[v] = max(dp[v], dp[to] + w[{v, to}]);
					res += dp[to] + w[{v, to}];
				}
			}
			
			ans.erase(ans.find(_res[v]));
			ans.insert(res);
			_res[v] = res;
			
			v = p[v];
		}
		
		last = *ans.rbegin();
		cout << last << '\n';
	}
}

main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
	}
}

Compilation message

diameter.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main(){
      | ^~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 16 ms 4956 KB Output is correct
3 Correct 72 ms 5096 KB Output is correct
4 Correct 138 ms 5456 KB Output is correct
5 Correct 11 ms 7004 KB Output is correct
6 Correct 40 ms 7476 KB Output is correct
7 Correct 131 ms 7468 KB Output is correct
8 Correct 249 ms 7764 KB Output is correct
9 Correct 48 ms 16692 KB Output is correct
10 Correct 82 ms 16780 KB Output is correct
11 Correct 232 ms 17044 KB Output is correct
12 Correct 419 ms 17612 KB Output is correct
13 Correct 104 ms 29384 KB Output is correct
14 Correct 152 ms 29640 KB Output is correct
15 Correct 342 ms 29640 KB Output is correct
16 Correct 593 ms 29880 KB Output is correct
17 Correct 1233 ms 29956 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -