Submission #1066133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066133		pan	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3943 ms	298120 KiB

diameter

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;


// This is grapevine but max length

// General
ll const MAXN = 100100;
ll n, q, u, v, w, t, maxw;
vector<pii> edges;
ll save[MAXN];
priority_queue<ll> ans, del;


// RURQ Segment Tree

struct node{

    int s, e, m; 
    pi val; 
    ll lazy; 
    node *l, *r; 
	node (int S, int E)
	{ 
       s = S, e = E, m = (s+e)/2;
       val = mp(0, s);
       lazy = 0; 
       if(s != e)
       { 
           l = new node(s, m); 
           r = new node(m+1, e); 
       }
 
    }
 
	void propogate()
	{
       if (lazy==0) return; 
       val.f+=lazy; 
       if (s != e){ 
           l->lazy+=lazy;
           r->lazy+=lazy;
       }
       lazy=0; 
    }
	void update(int S, int E, ll V)
	{ 
	   propogate();
       if(s==S && e==E) lazy += V; 
       else{ 
           if(E <= m) l->update(S, E, V); 
           else if (m < S) r->update(S, E, V); 
           else l->update(S, m, V),r->update(m+1, E, V);
           l->propogate(),r->propogate();
           val = max(l->val, r->val); 
       }
    }
	pi query(int S, int E)
	{
	   if (S > E) return mp(0LL, -1LL);
       propogate(); 
       if(s == S && e == E) return val; 
       if(E <= m) return l->query(S, E); 
       else if(S >= m+1) return r->query(S, E); 
       else return max(l->query(S, m), r->query(m+1, E)); 
   }

} *root[100005];
 

// centroid decomposition

ll label = -1;
ll sub[MAXN], lvl[MAXN], par[MAXN], m[MAXN], in[25][MAXN], out[25][MAXN], siz[MAXN];
vector<ll> V[MAXN];
bool vis[MAXN];
vector<ll> child[MAXN];

int dfs1(int u, int p, int l) {
	sub[u] = 1; // Subtree size is 1
	for (auto v : V[u]) {
		if (vis[u]) continue; // Already added to centroid tree
		if (v == p) continue;
		sub[u] += dfs1(v, u, l); // Increase size of subtree
	}
	return sub[u];
}
int dfs2(int u, int p, int n) { // Pass in the size of the subtree
	for (auto v : V[u]) {
		if (vis[u]) continue; // Already added to centroid tree
		if (v != p && sub[v] > n / 2) {
			return dfs2(v, u, n); // DFS to that node
		}
	}
	return u; // No child has size more than n/2, hence you are the centroid
}

void precomp(ll x, ll p = -1, ll l =0)
{
	in[l][x] = ++label;
	for (ll u: V[x]) if (u!=p && !vis[u]) precomp(u, x, l);
	out[l][x] = label;
}
// Building from node u, with a parent p and level l
void build(int u, int p=  -1, int l = 0) {
	int n = dfs1(u, p, l); // Find the size of each subtree
	int cent = dfs2(u, p, n); // Find the centroid
	label = -1;
	precomp(cent, -1, l);
	root[cent] = new node(0, label);
	//show(cent);
	siz[cent] = label+1;
	save[cent] = 0;
	ans.push(0);
	//show2(cent, label);
	vis[cent] = 1;
	//if (p == -1) p = cent; // Parent of root is yourself
	par[cent] = p; // Set the parent of centroid to the previous centroid
	lvl[cent] = l;
	for (auto v : V[cent]) {
		if (vis[v]) continue;
// If we have already added to centroid then we ignore
		child[cent].pb(v);
		build(v, cent, l + 1); // Recursively build each subtree
	}
}

//To construct the centroid tree, call build(root, -1, 0);


void set_weight(ll i, ll w)
{
	ll dw = w - edges[i].s;
	ll u = edges[i].f.f, v=edges[i].f.s;
	if (lvl[u] > lvl[v]) swap(u, v);
	ll now = u, l = lvl[u];
	while (now!= -1) 
	{
		//show(now);
		if (in[l][u] < in[l][v]) swap(u, v);
		del.push(save[now]);
		//show(2);
		//show3(in[l][u], out[l][u], siz[now]);
		root[now]->update(in[l][u], out[l][u], dw);
		//show(1);
		pi res = root[now]->query(0, siz[now]-1);
		ll lo = 0, hi  = child[now].size()-1;
		while (lo!=hi)
		{
			ll mid = (lo+hi+1)/2;
			if (in[l][child[now][mid]] <= res.s) lo = mid;
			else hi = mid-1;
		}
		pi res2 = root[now]->query(0, in[l][child[now][lo]]-1);
		res2= max(res2, root[now]->query(out[l][child[now][lo]]+1, siz[now]-1));
		save[now] = res.f + res2.f;
		ans.push(save[now]);
		now = par[now];
		l--;
	}
	edges[i].s = w;

}


int main()
{
	input3(n, q, maxw);
	for (ll i=0; i<n-1; ++i) vis[i] = 0;
	for (ll i=0; i<n-1; ++i)
	{
		input3(u, v, w);
		edges.pb(mp(mp(u, v), w));
		V[u].pb(v);
		V[v].pb(u);
	}
	//show(1);
	build(1, -1, 0);
	//show(1);
	for (ll i=0; i<n-1; ++i) 
	{
		ll val = edges[i].s;
		edges[i].s = 0;
		set_weight(i, val);
	}
	//show(1);
	ll hashing = 0;
	while (q--)
	{
		input2(u, w);
		u = (u + hashing)%(n-1);
		w = (w + hashing)%maxw;
		set_weight(u, w);
		while (del.size() && ans.top() == del.top()) 
		{
			ans.pop(); del.pop();
		}
		hashing = ans.top();
		print(hashing, '\n');
	}

	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:14:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:201:2: note: in expansion of macro 'input3'
  201 |  input3(n, q, maxw);
      |  ^~~~~~
diameter.cpp:14:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:205:3: note: in expansion of macro 'input3'
  205 |   input3(u, v, w);
      |   ^~~~~~
diameter.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
diameter.cpp:223:3: note: in expansion of macro 'input2'
  223 |   input2(u, w);
      |   ^~~~~~

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