제출 #1156745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156745		SmuggingSpun	Dynamic Diameter (CEOI19_diameter)	C++20	31 / 100	5029 ms	486920 KiB

diameter

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 1e5 + 5;
int n, q, u[lim], v[lim], w[lim];
ll ans = 0, BOUND_W;
vector<int>g[lim];
namespace sub12{
	const int lim = 5e3 + 5;
	int vertex;
	ll f[lim];
	void dfs(int s, int p){
		if(f[s] > f[vertex]){
			vertex = s;
		}
		for(int& i : g[s]){
			int d = u[i] ^ v[i] ^ s;
			if(d != p){
				f[d] = f[s] + w[i];
				dfs(d, s);
			}
		}
	}
	void solve(){
		for(int _ = 0; _ < q; _++){
			int d;
			ll e;
			cin >> d >> e;
			w[(ans + ll(d)) % (n - 1) + 1] = (ans + e) % BOUND_W;
			dfs(vertex = 1, f[1] = 0);
			dfs(vertex, f[vertex] = 0);
			cout << (ans = f[vertex]) << "\n";		
		}
	}
}
namespace sub3456{
	const ll INF = 1e18;
	bitset<lim>vis;
	vector<int>app[lim];
	multiset<ll>S_ans;
	ll last = 0;
	struct Centroid_Tree{
		map<int, int>low, tail, height, belong;
		vector<ll>f, lazy;
		vector<pair<ll, int>>st;
		vector<int>low_to_vertex;
		int N;
		ll opt;
		void dfs(const int root, int s, ll distance, int p = -1){
			low[s] = low.size() + 1;
			low_to_vertex.emplace_back(s);
			for(int& i : g[s]){
				int d = u[i] ^ v[i] ^ s;
				if(d != p && !vis.test(d)){
					f.emplace_back(distance + w[i]);
					app[i].emplace_back(root);
					belong[d] = ((height[d] = height[s] + 1) == 1 ? d : belong[s]);
					dfs(root, d, f.back(), s);
				}
			}
			tail[s] = low.size(); 
		}
		void build(int id, int l, int r){
			if(l == r){
				st[id] = make_pair(f[l], low_to_vertex[l]);
				return;
			}
			int m = (l + r) >> 1;
			build(id << 1, l, m);
			build(id << 1 | 1, m + 1, r);
			st[id] = max(st[id << 1], st[id << 1 | 1]);
		}
		void push_down(int id){
			st[id << 1].first += lazy[id];
			st[id << 1 | 1].first += lazy[id];
			lazy[id << 1] += lazy[id];
			lazy[id << 1 | 1] += lazy[id];
			lazy[id] = 0;
		}
		void update(int id, int l, int r, int u, int v, ll x){
			if(l > v || r < u){
				return;
			}
			if(u <= l && v >= r){
				st[id].first += x;
				lazy[id] += x;
				return;
			}
			push_down(id);
			int m = (l + r) >> 1;
			update(id << 1, l, m, u, v, x);
			update(id << 1 | 1, m + 1, r, u, v, x);
			st[id] = max(st[id << 1], st[id << 1 | 1]);
		}
		pair<ll, int>get(int id, int l, int r, int u, int v){
			if(l > v || r < u){
				return make_pair(-INF, 0);
			}
			if(u <= l && v >= r){
				return st[id];
			}
			push_down(id);
			int m = (l + r) >> 1;
			return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
		}
		void init(int root){
			vis.set(root);
			low_to_vertex.emplace_back(-1);
			f.emplace_back(-1);
			f.emplace_back(0);
			dfs(root, root, height[root] = 0);
			N = int(f.size()) - 1;
			st.assign(N << 2, make_pair(-INF, 0));
			lazy.assign(N << 2, 0LL);
			build(1, 1, N);
			if(st[1].first > 0){
				int d = belong[st[1].second];
				S_ans.insert(opt = st[1].first + max(get(1, 1, N, 1, low[d] - 1).first, get(1, 1, N, tail[d] + 1, N).first));
			}
		}
		void query(int d, ll e){
			int vertex = (height[u[d]] < height[v[d]] ? v[d] : u[d]);
			update(1, 1, N, low[vertex], tail[vertex], e - w[d]);
			S_ans.erase(S_ans.find(opt));
			int D = belong[st[1].second];
			S_ans.insert(opt = st[1].first + max(get(1, 1, N, 1, low[D] - 1).first, get(1, 1, N, tail[D] + 1, N).first));
		}
	};
	Centroid_Tree tree[lim];
	int cnt_child[lim];
	void dfs(int s, int p = -1){
		cnt_child[s] = 1;
		for(int& i : g[s]){
			int d = u[i] ^ v[i] ^ s;
			if(d != p && !vis.test(d)){
				dfs(d, s);
				cnt_child[s] += cnt_child[d];
			}
		}
	}
	void centroid_decomposition(int s){
		dfs(s);
		int N = cnt_child[s], parent = -1;
		while(true){
			bool change = false;
			for(int& i : g[s]){
				int d = u[i] ^ v[i] ^ s;
				if(d != parent && !vis.test(d) && cnt_child[d] > (N >> 1)){
					parent = s;
					s = d;
					change = true;
					break;
				}
			}
			if(!change){
				break;
			}
		} 
		tree[s].init(s);
		for(int& i : g[s]){
			int d = u[i] ^ v[i] ^ s;
			if(!vis.test(d)){
				centroid_decomposition(d);
			}
		}
	}
	void solve(){
		vis.reset();
		centroid_decomposition(1);
		for(int _ = 0; _ < q; _++){
			int d;
			ll e;
			cin >> d >> e;
			d = (last + ll(d)) % (n - 1) + 1;
			e = (last + e) % BOUND_W;
			for(int& i : app[d]){
				tree[i].query(d, e);
			}
			w[d] = e;
			cout << (last = *S_ans.rbegin()) << "\n";
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> q >> BOUND_W;
	for(int i = 1; i < n; i++){
		cin >> u[i] >> v[i] >> w[i];
		g[u[i]].emplace_back(i);
		g[v[i]].emplace_back(i);
	}
	if(max(n, q) <= 5000){
		sub12::solve();
	}
	else{
		sub3456::solve();
	}
}

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

diameter.cpp: In function 'int main()':
diameter.cpp:193:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27