Submission #373245

#	Time	Username	Problem	Language	Result	Execution time	Memory
373245		luciocf	Dynamic Diameter (CEOI19_diameter)	C++14	0 / 100	5058 ms	70184 KiB

diameter

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5+10;
const ll inf = 2e18+10;

int n;
int st[maxn], en[maxn], tt;

vector<int> grafo[maxn];

struct SegmentTree
{
	pair<ll, int> tree[4*maxn];
	ll lazy[4*maxn];

	void build(int node, int l, int r)
	{
		tree[node].ss = l;
		if (l == r) return;

		int mid = (l+r)>>1;

		build(2*node, l, mid); build(2*node+1, mid+1, r);
	}

	void flush(int node, int l, int r)
	{
		if (!lazy[node]) return;

		if (l != r)
			lazy[2*node] += lazy[node], lazy[2*node+1] += lazy[node];

		tree[node].ff += lazy[node];
		lazy[node] = 0;
	}

	void upd(int node, int l, int r, int a, int b, ll v)
	{
		flush(node, l, r);
		if (l > b || r < a) return;
		
		if (l >= a && r <= b)
		{
			lazy[node] = v;
			flush(node, l, r);
			return;
		}

		int mid = (l+r)>>1;

		upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

		tree[node] = max(tree[2*node], tree[2*node+1]);
	}

	ll query(int node, int l, int r, int pos)
	{
		flush(node, l, r);
		if (l == r) return tree[node].ff;

		int mid = (l+r)>>1;

		if (pos <= mid) return query(2*node, l, mid, pos);
		return query(2*node+1, mid+1, r, pos);
	}
} seg;

struct BinaryLifting
{
	int tab[maxn][20], nivel[maxn];

	void dfs(int u, int p)
	{
		for (auto v: grafo[u])
		{
			if (v == p) continue;

			nivel[v] = nivel[u]+1, tab[v][0] = u;
			dfs(v, u);
		}
	}

	void build(int n)
	{
		for (int j = 1; j < 20; j++)
			for (int i = 1; i <= n; i++)
				tab[i][j] = tab[tab[i][j-1]][j-1];
	}

	int lca(int u, int v)
	{
		if (nivel[u] < nivel[v]) swap(u, v);

		for (int i = 19; i >= 0; i--)
			if (nivel[u]-(1<<i) >= nivel[v])
				u = tab[u][i];

		if (u == v) return u;

		for (int i = 19; i >= 0; i--)
			if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
				u = tab[u][i], v = tab[v][i];

		return tab[u][0];
	}

	ll dist(int u, int v)
	{
		int l = lca(u, v);

		return seg.query(1, 1, n, st[u]) + seg.query(1, 1, n, st[v]) - 2ll*seg.query(1, 1, n, st[l]);
	}
} LCA;


struct Node
{
	Node *l, *r;
	ll v;

	Node()
	{
		l = r = NULL;
		v = 0;
	}
};

struct SparseSegmentTree
{
	Node *root;

	ll get(Node *node)
	{
		return (node ? node->v : 0);
	}

	void upd(Node *node, int l, int r, int pos, int v)
	{
		if (l == r)
		{
			node->v = v;
			return;
		}

		int mid = (l+r)>>1;

		if (pos <= mid)
		{
			if (!node->l) node->l = new Node();
			upd(node->l, l, mid, pos, v);
		}
		else
		{
			if (!node->r) node->r = new Node();
			upd(node->r, mid+1, r, pos, v);
		}

		node->v = max(get(node->l), get(node->r));
	}

	ll query(Node *node, int l, int r, int a, int b)
	{
		if (!node || a > b || l > b || r < a) return 0;
		if (l >= a && r <= b) return node->v;

		int mid = (l+r)>>1;

		return max(query(node->l, l, mid, a, b), query(node->r, mid+1, r, a, b));
	}
};

struct Centroid
{
	int sz[maxn];
	bool mark[maxn];

	int pai[maxn], edge_pai[maxn];
	vector<int> tree[maxn];

	int in[maxn], out[maxn], tempo;
	SparseSegmentTree seg_c[maxn];

	void dfs(int u, int p)
	{
		sz[u] = 1;

		for (auto v: grafo[u])
		{
			if (v == p || mark[v]) continue;

			dfs(v, u);
			sz[u] += sz[v];
		}
	}

	int centroid(int u, int p, int S)
	{
		for (auto v: grafo[u])
			if (v != p && !mark[v] && sz[v] > S/2)
				return centroid(v, u, S);

		return u;
	}

	int decompose(int u)
	{
		dfs(u, 0);
		int c = centroid(u, 0, sz[u]);
		mark[c] = 1;

		for (auto v: grafo[c])
		{
			if (!mark[v])
			{
				int c2 = decompose(v);

				tree[c].push_back(c2);
				tree[c2].push_back(c);
			}
		}

		return c;
	}

	void init(int n)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < tree[i].size(); j++)
			{
				if (tree[i][j] == pai[i])
				{
					swap(tree[i][j], tree[i].back());
					tree[i].pop_back();
				}
			}
		}
	}

	void calc(int u, int p)
	{
		in[u] = ++tempo;

		for (int i = 0; i < tree[u].size(); i++)
		{
			int v = tree[u][i];
			if (v == p) continue;

			pai[v] = u, edge_pai[v] = i;
			calc(v, u);
		}

		out[u] = tempo;
	}

	vector<int> get_list(int a, int b)
	{
		vector<int> V;
		int u = 1, p = 0, e = 0;

		while (true)
		{
			V.push_back(u);

			bool ok = 0;

			for (int i = 0; i < tree[u].size(); i++)
			{
				int v = tree[u][i];
				if (v == p) continue;

				int k = (a == u ? b : a);

				if (LCA.nivel[k] < LCA.nivel[u])
				{
					if (LCA.nivel[v] < LCA.nivel[u])
					{
						p = u, u = v;
						ok = 1;
						break;
					}
				}
				else
				{
					if (LCA.nivel[v] > LCA.nivel[u] && LCA.lca(k, v) != u)
					{
						p = u, u = v;
						ok = 1;
						break;
					}
				}
			}

			if (!ok)
				break;
		}

		return V;
	}

	void upd(int v)
	{
		while (v != 1)
		{
			int u = pai[v];
			ll D = LCA.dist(u, v);

			if (!seg_c[u].root) seg_c[u].root = new Node();
			seg_c[u].upd(seg_c[u].root, 1, n, in[v], D);

			v = u;
		}
	}

	ll get(int v)
	{
		ll ans = seg_c[v].query(seg_c[v].root, 1, n, 1, n);

		int e = edge_pai[v];
		int u = pai[v];

		while (u)
		{
			ll ans1 = 0, ans2 = 0;
			ll D = LCA.dist(u, v);

			ans = max(ans, D);

			if (e > 0)
			{
				int l = in[tree[u][0]], r = out[tree[u][e-1]];
				ans1 = D + seg_c[u].query(seg_c[u].root, 1, n, l, r);
			}

			if (e < (int)tree[u].size()-1)
			{
				int l = in[tree[u][e+1]], r = out[tree[u].back()];

				ans2 = D + seg_c[u].query(seg_c[u].root, 1, n, l, r);
			}

			ans = max({ans, ans1, ans2});

			e = edge_pai[u];
			u = pai[u];
		}

		return ans;
	}
} CD;

struct Edge
{
	int u, v;
	ll w;
} edge[maxn];

void dfs(int u, int p)
{
	st[u] = ++tt;

	for (auto v: grafo[u])
		if (v != p)
			dfs(v, u);

	en[u] = tt;
}

int main(void)
{
	int q;
	ll limit;
	scanf("%d %d %lld", &n, &q, &limit);

	for (int i = 1; i < n; i++)
	{
		int u, v;
		ll w;

		scanf("%d %d %lld", &u, &v, &w);

		grafo[u].push_back(v);
		grafo[v].push_back(u);

		edge[i] = {u, v, w};
	}

	dfs(1, 0);
	LCA.dfs(1, 0); LCA.build(n);
	CD.decompose(1); CD.init(n); CD.calc(1, 0);
	seg.build(1, 1, n);

	for (int i = 1; i < n; i++)
	{
		int u = edge[i].u, v = edge[i].v;
		if (LCA.nivel[u] < LCA.nivel[v]) swap(u, v);

		seg.upd(1, 1, n, st[u], en[u], edge[i].w);
	}

	for (int i = 1; i <= n; i++)
		CD.upd(i);

	ll last = 0;

	for (int i = 1; i <= q; i++)
	{
		int e;
		ll w;
		scanf("%d %lld", &e, &w);

		e = (1ll*e + last)%(n-1);
		w = (w + last)%limit;

		e++;

		int u = edge[e].u, v = edge[e].v;
		if (LCA.nivel[u] < LCA.nivel[v]) swap(u, v);

		seg.upd(1, 1, n, st[u], en[u], w - edge[e].w);
		edge[e].w = w;

		vector<int> V = CD.get_list(u, v);
		
		for (auto k: V)
			CD.upd(k);

		seg.flush(1, 1, n);
		int p = seg.tree[1].ss;

		last = CD.get(p);

		printf("%lld\n", last);
	}
}

Compilation message (stderr)

diameter.cpp: In member function 'void Centroid::init(int)':
diameter.cpp:237:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |    for (int j = 0; j < tree[i].size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~
diameter.cpp: In member function 'void Centroid::calc(int, int)':
diameter.cpp:252:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  252 |   for (int i = 0; i < tree[u].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~
diameter.cpp: In member function 'std::vector<int> Centroid::get_list(int, int)':
diameter.cpp:275:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  275 |    for (int i = 0; i < tree[u].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~
diameter.cpp:267:21: warning: unused variable 'e' [-Wunused-variable]
  267 |   int u = 1, p = 0, e = 0;
      |                     ^
diameter.cpp: In function 'int main()':
diameter.cpp:381:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  381 |  scanf("%d %d %lld", &n, &q, &limit);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:388:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  388 |   scanf("%d %d %lld", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:418:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  418 |   scanf("%d %lld", &e, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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