Submission #207928

#	Time	Username	Problem	Language	Result	Execution time	Memory
207928		E869120	Dynamic Diameter (CEOI19_diameter)	C++14	11 / 100	5090 ms	1048580 KiB

diameter

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	long long val, lazy;
	int cl, cr, dep;
};

class LazySegmentTree {
public:
	int depth_ = 0;
	int size_ = 1;
	vector<Node> G;

	void init(int sz) {
		while (size_ <= sz) { size_ *= 2; depth_++; }
		G.push_back(Node{ 0LL, 0LL, -1, -1, depth_ * 2 });
	}
	void refresh(int pos) {
		if (G[pos].dep >= 1) {
			if (G[pos].cl == -1) { G[pos].cl = G.size(); G.push_back(Node{ 0LL, 0LL, -1, -1, G[pos].dep - 1 }); }
			if (G[pos].cr == -1) { G[pos].cr = G.size(); G.push_back(Node{ 0LL, 0LL, -1, -1, G[pos].dep - 1 }); }
			G[G[pos].cl].lazy += G[pos].lazy;
			G[G[pos].cr].lazy += G[pos].lazy;
			G[pos].lazy = 0;
			G[pos].val = max(G[G[pos].cl].val + G[G[pos].cl].lazy, G[G[pos].cr].val + G[G[pos].cr].lazy);
		}
		else {
			G[pos].val += G[pos].lazy;
			G[pos].lazy = 0;
		}
	}
	void add_(int lx, int rx, int ly, int ry, long long x, int ax, int bx, int ay, int by, int u) {
		if (bx <= lx || rx <= ax || by <= ly || ry <= ay) return;
		if (lx <= ax && bx <= rx && ly <= ay && by <= ry) { G[u].lazy += x; return; }
		refresh(u);
		if (G[u].dep >= depth_ + 1) {
			add_(lx, rx, ly, ry, x, ax, bx, ay, (ay + by) >> 1, G[u].cl);
			add_(lx, rx, ly, ry, x, ax, bx, (ay + by) >> 1, by, G[u].cr);
		}
		else {
			add_(lx, rx, ly, ry, x, ax, (ax + bx) >> 1, ay, by, G[u].cl);
			add_(lx, rx, ly, ry, x, (ax + bx) >> 1, bx, ay, by, G[u].cr);
		}
		refresh(u);
	}
	void add(int lx, int rx, int ly, int ry, long long x) {
		add_(lx, rx, ly, ry, x, 0, size_, 0, size_, 0);
	}
	long long getans() {
		return G[0].val + G[0].lazy;
	}
};

long long N, A[1 << 18], B[1 << 18], C[1 << 18];
long long Q, D[1 << 18], E[1 << 18];
long long W;
vector<int> X[1 << 18];

int cl[1 << 18], cr[1 << 18], depth[1 << 18], cnts;
LazySegmentTree Z;

void dfs(int pos, int dep) {
	cnts++; cl[pos] = cnts; depth[pos] = dep;
	for (int i : X[pos]) {
		if (cl[i] == 0) dfs(i, dep + 1);
	}
	cr[pos] = cnts;
}

int main() {
	scanf("%lld%lld%lld", &N, &Q, &W);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= Q; i++) scanf("%lld%lld", &D[i], &E[i]);
	dfs(1, 0);
	Z.init(N + 2);

	for (int i = 1; i <= N - 1; i++) {
		if (depth[A[i]] > depth[B[i]]) swap(A[i], B[i]);
		Z.add(cl[B[i]], cr[B[i]] + 1, 1, N + 1, C[i]);
		Z.add(cl[B[i]], cr[B[i]] + 1, cl[B[i]], cr[B[i]] + 1, -C[i]);

		Z.add(1, N + 1, cl[B[i]], cr[B[i]] + 1, C[i]);
		Z.add(cl[B[i]], cr[B[i]] + 1, cl[B[i]], cr[B[i]] + 1, -C[i]);
	}

	long long last = 0;
	for (int i = 1; i <= Q; i++) {
		D[i] = (D[i] + last) % (N - 1) + 1;
		E[i] = (E[i] + last) % W;

		int pos = B[D[i]];
		Z.add(cl[pos], cr[pos] + 1, 1, N + 1, E[i] - C[D[i]]);
		Z.add(cl[pos], cr[pos] + 1, cl[pos], cr[pos] + 1, C[D[i]] - E[i]);

		Z.add(1, N + 1, cl[pos], cr[pos] + 1, E[i] - C[D[i]]);
		Z.add(cl[pos], cr[pos] + 1, cl[pos], cr[pos] + 1, C[D[i]] - E[i]);
		C[D[i]] = E[i];
		long long rem = Z.getans();
		last = rem;
		printf("%lld\n", rem);
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
diameter.cpp: In function 'int main()':
diameter.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &N, &Q, &W);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:81:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) scanf("%lld%lld", &D[i], &E[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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