제출 #716460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716460		faribourz	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	775 ms	17592 KiB

diameter

// 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';
//		}
//	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27