Submission #1266431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266431		gumball1	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	3019 ms	268696 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
#define endl '\n'
const int N = 1e5 + 5;
const int INF = 1e18 + 1;
const int MAXN = 3e3 + 5;
const int MOD = 1e9 + 7;
const int LOG = 20;
int n , q , we;
vector<pii> adj[N];
int dist[N];
int timer;
int tin[N];
int tout[N];
int id[N];
int a[N];
int lazy[4 * N];
int parent[N];
multiset<int> vv[N + 2];
multiset<int> ss;
struct edge{
	int u , v , w;
} edges[N];

struct ST{
	vector<int> st, lazy;
	void init(int m){
		st.assign(4 * m + 5 , 0);
		lazy.assign(4 * m + 4 , 0);
	}
	void down(int idx){
     	int k = lazy[idx];
	    if(k == 0) return;
	    st[2 * idx] += k;
	    st[2 * idx + 1] += k;
	    lazy[2 * idx] += k;
	    lazy[2 * idx + 1] += k;
	    lazy[idx] = 0;
    }
    void update(int idx , int l , int r , int u , int v , int val){
	   if(l > v || r < u) return;
	   if(u <= l && r <= v){
		   st[idx] += val;
		   lazy[idx] += val;
		   return; 
	   }
	   down(idx);
	   int mid = (l + r) / 2;
	   update(2 * idx , l , mid, u , v , val);
	   update(2 * idx + 1 , mid + 1 , r , u , v , val);
	   st[idx] = max(st[2 * idx] , st[2 * idx + 1]);
   }   
   int get(int idx , int l , int r , int u , int v){
     	if(l > v || r < u) return 0;
    	if(u <= l && r <= v){
	    	return st[idx];
    	}
	    int mid = (l + r) / 2;
        return max(get(2 * idx , l , mid , u , v) , get(2 * idx + 1 , mid + 1 , r , u , v));
   }
} segtree[LOG + 5];

struct Centroid{
	int sz[N];
	int done[N];
	int t = 0;
	int cntnodeatdepth[LOG + 5];
	int tin[N + 5][LOG + 5];
	int tout[N + 5][LOG + 5];
	int par[N + 5][LOG + 5];
	vector<pii> mngoc[N + 5];
	void dfs(int u , int p){
		t++;
		sz[u] = 1;
		for(auto v : adj[u]){
			if(v.first != p && !done[v.first]){
				dfs(v.first , u);
				sz[u] += sz[v.first];
			}
		}
	}
	int findcentroid(int u , int p){
        for(auto v : adj[u]){
            if(v.first != p && !done[v.first]){
               if(sz[v.first] > t / 2) return findcentroid(v.first , u);
            }
        }
        return u;
    }

	void dfs2(int depth , int root , int u , int p , int cost){
		tin[u][depth] = ++cntnodeatdepth[depth];
		segtree[depth].update(1 , 1 , n , tin[u][depth] , tin[u][depth] , cost);
		mngoc[u].push_back({depth , root});
		for(auto v : adj[u]){
			if(v.first == p || done[v.first]) continue;
			if(u == p){
				par[v.first][depth] = v.first;
			}
			else{
				par[v.first][depth] = par[u][depth];
			}
			dfs2(depth , root , v.first , u , cost + v.second);
		}
		tout[u][depth] = cntnodeatdepth[depth];
	}
    
	int get(int u){
		if(!vv[u].size()) return 0;
		auto it = prev(vv[u].end());
		if(vv[u].size() == 1) return *it;
		else return *it + *prev(it);
	}
	
		
	void decompose(int dep , int u){
		t = 0;
		dfs(u , u);
		u = findcentroid(u , u);
		dfs2(dep , u , u , u , 0);
	    for(auto v : adj[u]){
	    	if(!done[v.first] && tin[v.first][dep]) {
               vv[u].insert(segtree[dep].get(1 , 1 , n , tin[v.first][dep] , tout[v.first][dep]));
             }

		}
		ss.insert(get(u));
		done[u] = 1;
		for(auto v : adj[u]){
			if(!done[v.first]){
				decompose(dep + 1 , v.first);
			}
		}
	}
	
	void update(int dep , int root,  int u , int v , int val){
		 if(!tin[u][dep] || !tin[v][dep]) return;
		 if(tin[u][dep] < tin[v][dep]) swap(u , v);
     	 ss.erase(ss.find(get(root)));
		 vv[root].erase(vv[root].find(segtree[dep].get(1 , 1 , n , tin[par[u][dep]][dep] ,  tout[par[u][dep]][dep])));
		 segtree[dep].update(1 , 1 , n, tin[u][dep] , tout[u][dep] , val);
		 vv[root].insert(segtree[dep].get(1 , 1 , n ,tin[par[u][dep]][dep] ,  tout[par[u][dep]][dep] ));
		 ss.insert(get(root));
	}
	
	void update(int u , int v , int val){
		for(auto r : mngoc[u]){
			update(r.first , r.second , u , v , val);
		}
	}
	
} centroid;


void solve(void){
	cin >> n >> q >> we; 
	for(int i = 0 ; i < n - 1 ; i++){
		int u , v , w; cin >> u >> v >> w;
		adj[u].push_back({v , w});
		adj[v].push_back({u , w});
		edges[i] = {u , v , w};
	}
	for(int i = 0 ; i <= LOG ; i++) segtree[i].init(n);
	centroid.decompose(0 , 1);
	int res = 0;
    while(q--){
    	int d , e; cin >> d >> e;
    	d = (d + res) % (n - 1);
    	e = (e + res) % we;
      	centroid.update(edges[d].u , edges[d].v , e - edges[d].w);
      	edges[d].w = e;
      	res = *prev(ss.end());
		cout << res << endl;
	}
	
	
	
	
}


signed main(void){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
//    if(fopen("TASK.INP" , "r")){
//        freopen("TASK.INP" , "r" , stdin);
//        freopen("TASK.OUT" , "w" , stdout);
//    }
    solve();
    return 0;
}

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