Submission #373245

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
373245	2021-03-03T22:43:08 Z	luciocf	Dynamic Diameter (CEOI19_diameter)	C++14	0 / 100	5000 ms	70184 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	11372 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	11372 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	11372 KB	Output is correct
2	Correct	7 ms	11372 KB	Output is correct
3	Correct	10 ms	11372 KB	Output is correct
4	Correct	37 ms	11628 KB	Output is correct
5	Correct	161 ms	12524 KB	Output is correct
6	Correct	8 ms	11372 KB	Output is correct
7	Correct	9 ms	11500 KB	Output is correct
8	Correct	11 ms	11500 KB	Output is correct
9	Correct	42 ms	11500 KB	Output is correct
10	Correct	368 ms	11756 KB	Output is correct
11	Correct	1765 ms	13104 KB	Output is correct
12	Correct	16 ms	12780 KB	Output is correct
13	Correct	55 ms	12780 KB	Output is correct
14	Correct	343 ms	12908 KB	Output is correct
15	Correct	3381 ms	13356 KB	Output is correct
16	Execution timed out	5058 ms	13948 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-