oj.uz

Submission #716460

# Submission time Handle Problem Language Result Execution time Memory
716460 2023-03-30T06:33:29 Z faribourz Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 775 ms 17592 KB 
// Only GOD
// Believe in yourself!
// -o Sango zadam be shishe 
// -o Comeback bezan hamishe!

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

#define pb push_back
#define F first
#define S second
#define bit(x, y) (x >> y)&1
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define int ll
#define mid ((l+r)>>1)
#define lid (id << 1)
#define rid (lid | 1)
const int N = 3e5+10;
const int INF = 1e9+10;
int n, q, W;
vector<pii> G[N];
int edge[N], dp[N], maxout[N], lst, h[N];
//pii EDGE[N];
//map<pii, int> E;
//// chinese seg:)
//void upd(int id){
//	int mx1 = maxout[lid] + E[{id, lid}], mx2 = maxout[rid] + E[{id, rid}];
//	maxout[id] = max(mx1, mx2);
//	dp[id] = mx1 + mx2;
//	lst = max({lst, dp[id], dp[rid], dp[lid]});
//	id >>= 1;
//	for(; id > 0; id >>= 1){
//		int mx1 = maxout[lid] + E[{id, lid}], mx2 = maxout[rid] + E[{id, rid}];
//		maxout[id] = max(mx1, mx2);
//		dp[id] = mx1 + mx2;
//		lst = max({lst, dp[id], dp[rid], dp[lid]});
//	}
//}
void DFS(int v, int p = -1){
	int mx1 = -1, mx2 = -1;
	for(auto x : G[v]){
		if(x.F == p)
			continue;
		h[x.F] = h[v] + 1;
		DFS(x.F, v);
		if(edge[x.S] + maxout[x.F] >= mx1){
			swap(mx1, mx2);
			mx1 = edge[x.S] + maxout[x.F]; 
		}
		else if(edge[x.S] + maxout[x.F] > mx2){
			mx2 = edge[x.S] + maxout[x.F]; 
		}
	}
	maxout[v] = (mx1==-1 ? 0 : mx1);
	if(mx2 != -1){
		dp[v] = mx1 + mx2;
	}
}
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q >> W;
	bool f = 0;
	for(int i = 0; i < n-1; i++){
		int v, u, w;
		cin >> v >> u >> w;
		G[v].pb({u, i});
		G[u].pb({v, i});
		if(v != 1 && u != 1)
			f = 1;
		edge[i] = w;
	//	EDGE[i]={v, u};
	//	E[{v, u}]=w;
	//	E[{u, v}]=w;
	}	
	lst = 0;
	if(n <= 5001 && q <= 5001){
		while(q--){
			int d, e;
			cin >> d >> e;
			edge[(d+lst)%(n-1)] = (e+lst)%W;
			DFS(1);
			lst = 0;
			for(int i = 1; i <= n; i++)
				lst = max({lst, dp[i], maxout[i]});
			cout << lst << '\n';
		}
	}
	else{
		set<pii> s;
		for(int i = 0; i < n-1; i++){
			s.insert({edge[i], i});
		}
		while(q--){
			int d, e;
			cin >> d >> e;
			int XX = (d+lst)%(n-1), YY = (e+lst)%W;
			s.erase({edge[XX], XX});
			edge[XX] = YY;
			s.insert({edge[XX], XX});
			auto itr = s.rbegin();
			lst = (*itr).F;
			itr--;
			lst += (*itr).F;
			cout << lst << '\n';
		}
	}
//	else{
//		DFS(1);
//		while(q--){
//			int d, e;
//			cin >> d >> e;
//			edge[(d+lst)%(n-1)] = (e+lst)%W;
//			int v = EDGE[(d+lst)%(n-1)].F, u = EDGE[(d+lst)%(n-1)].S;
//			E[{v, u}] = (e+lst)%W;
//			E[{u, v}] = E[{v, u}];
//			if(u < v)
//				swap(v, u);
//			lst = 0;
//			upd(v);
//			cout << lst << '\n';
//		}
//	}
}

Compilation message

diameter.cpp: In function 'int32_t main()':
diameter.cpp:69:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   69 |  bool f = 0;
      |       ^

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7396 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7384 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 5 ms 7392 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 6 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 5 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 86 ms 7500 KB Output is correct
20 Correct 89 ms 7580 KB Output is correct
21 Correct 97 ms 7472 KB Output is correct
22 Correct 117 ms 7488 KB Output is correct
23 Correct 674 ms 7728 KB Output is correct
24 Correct 697 ms 7756 KB Output is correct
25 Correct 775 ms 7888 KB Output is correct
26 Correct 770 ms 8148 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Incorrect 12 ms 7408 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7468 KB Output is correct
2 Incorrect 9 ms 7508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7396 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7384 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 5 ms 7392 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 6 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 5 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 86 ms 7500 KB Output is correct
20 Correct 89 ms 7580 KB Output is correct
21 Correct 97 ms 7472 KB Output is correct
22 Correct 117 ms 7488 KB Output is correct
23 Correct 674 ms 7728 KB Output is correct
24 Correct 697 ms 7756 KB Output is correct
25 Correct 775 ms 7888 KB Output is correct
26 Correct 770 ms 8148 KB Output is correct
27 Correct 4 ms 7380 KB Output is correct
28 Correct 4 ms 7380 KB Output is correct
29 Correct 5 ms 7380 KB Output is correct
30 Incorrect 12 ms 7408 KB Output isn't correct
31 Halted 0 ms 0 KB -