Submission #420062

#	Time	Username	Problem	Language	Result	Execution time	Memory
420062		AriaH	Dynamic Diameter (CEOI19_diameter)	C++11	100 / 100	432 ms	69564 KiB

diameter

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 3e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

ll W, last, H[N], lz[N << 2], E[N];

int n, q, A[N], B[N], pos[N], St[N], Fi[N];

vector < pll > G[N];

vector < int > tour;

struct node
{
	ll mx, mn, ab, bc, abc; /// ab -> maximum a - 2b dar in node, bc -> maximum -2b + c, abc max a + c - 2b
	void init(ll x)
	{
		mx = mn = x;
		ab = bc = -x;
		abc = 0;
	}
	friend node operator | (node a, node b)
	{
		node ret;
		ret.mx = max(a.mx, b.mx);
		ret.mn = min(a.mn, b.mn);
		ret.ab = max({a.ab, b.ab, a.mx - 2 * b.mn});
		ret.bc = max({a.bc, b.bc, - 2 * a.mn + b.mx});
		ret.abc = max({a.abc, b.abc, a.ab + b.mx, a.mx + b.bc});
		return ret;
	}
	friend node operator + (node V, ll x)
	{
		V.mx += x, V.mn += x, V.ab -= x, V.bc -= x;
		return V;
	}
} seg[N << 2], Q;

void dfs(int v, int P = 0)
{
	///printf("v = %d H = %lld\n", v, H[v]);
	tour.push_back(v);
	for(auto y : G[v])
	{
		ll u = y.F, cost = y.S;
		if(u == P) continue;
		H[u] = H[v] + cost;
		dfs(u, v);
		tour.push_back(v);
	}
}

void build(int v = 1, int tl = 0, int tr = SZ(tour) - 1)
{
	if(tl == tr)
	{
		seg[v].init(H[tour[tl]]);
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] | seg[v << 1 | 1];
}

void S(int v, int tl, int tr)
{
	if(!lz[v] || tl == tr) return;
	lz[v << 1] += lz[v];
	lz[v << 1 | 1] += lz[v];
	seg[v << 1] = seg[v << 1] + lz[v];
	seg[v << 1 | 1] = seg[v << 1 | 1] + lz[v];
	lz[v] = 0;
}

void upd(int l, int r, ll x, int v = 1, int tl = 0, int tr = SZ(tour) - 1)
{
	S(v, tl, tr);
	if(l > tr || r < tl || l > r) return;
	if(l <= tl && tr <= r)
	{
		seg[v] = seg[v] + x;
		lz[v] += x;
		///printf("here l = %d r = %d x = %lld\n", l, r, x);
		return;
	}
	int mid = (tl + tr) >> 1;
	upd(l, r, x, v << 1, tl, mid), upd(l, r, x, v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] | seg[v << 1 | 1];
}

/*void get(int l, int r, int v = 1, int tl = 0, int tr = SZ(tour) - 1)
{
	S(v, tl, tr);
	if(l > tr || r < tl || l > r) return;
	if(l <= tl && tr <= r)
	{
		if(Q.mx == -inf) Q = seg[v];
		else Q = Q | seg[v];
		return;
	}
	int mid = (tl + tr) >> 1;
	get(l, r, v << 1, tl, mid), get(l, r, v << 1 | 1, mid + 1, tr);
}
*/

int main()
{
	scanf("%d%d%lld", &n, &q, &W);
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		ll c;
		scanf("%d%d%lld", &a, &b, &c);
		G[a].push_back(Mp(b, c));
		G[b].push_back(Mp(a, c));
		A[i] = a, B[i] = b;
		E[i] = c;
	}
	dfs(1);
	for(int i = 0; i < SZ(tour); i ++)
	{
		Fi[tour[i]] = i;
	}
	for(int i = SZ(tour) - 1; ~i; i --)
	{
		St[tour[i]] = i;
	}
	for(int i = 1; i < n; i ++)
	{
		if(H[B[i]] > H[A[i]]) swap(A[i], B[i]);
	}
	/*for(int i = 1; i <= n ;i ++)
	{
		printf("%d %d %d\n", i, St[i], Fi[i]);
	}
	*/
	build();
	while(q --)
	{
		ll fir, sec;
		scanf("%lld%lld", &fir, &sec);
		fir = (fir + last) % (n - 1) + 1;
		sec = (sec + last) % W;
		///printf("fir = %lld sec = %lld\n", fir, sec);
		upd(St[A[fir]], Fi[A[fir]], sec - E[fir]);
		E[fir] = sec;
		last = seg[1].abc;
		printf("%lld\n", last);
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d%d%lld", &n, &q, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d%d%lld", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |   scanf("%lld%lld", &fir, &sec);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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