Submission #207972

#	Time	Username	Problem	Language	Result	Execution time	Memory
207972		E869120	Dynamic Diameter (CEOI19_diameter)	C++14	55 / 100	2382 ms	44028 KiB

diameter

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

class LazySegmentTree {
public:
	int size_ = 1;
	vector<long long> dat, lazy;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, 0);
		lazy.resize(size_ * 2, 0);
	}
	void refresh(int u) {
		if (u < size_) {
			lazy[u * 2 + 0] += lazy[u];
			lazy[u * 2 + 1] += lazy[u];
			lazy[u] = 0;
			dat[u] = max(dat[u * 2] + lazy[u * 2], dat[u * 2 + 1] + lazy[u * 2 + 1]);
		}
		else {
			dat[u] += lazy[u];
			lazy[u] = 0;
		}
	}
	void add_(int l, int r, long long x, int a, int b, int u) {
		if (l <= a && b <= r) { lazy[u] += x; return; }
		if (r <= a || b <= l) return;
		refresh(u);
		add_(l, r, x, a, (a + b) >> 1, u * 2);
		add_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
		refresh(u);
	}
	void add(int l, int r, long long x) {
		add_(l, r, x, 0, size_, 1);
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u] + lazy[u];
		if (r <= a || b <= l) return -(1LL << 60);
		refresh(u);
		long long v1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		refresh(u);
		return max(v1, v2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

// Input
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<pair<int, long long>> X[1 << 18];

// Some Information
long long dist[1 << 18];

// Subtask 2
void dfs1(int pos, long long dep) {
	dist[pos] = dep;
	for (int i = 0; i < X[pos].size(); i++) {
		if (dist[X[pos][i].first] != (1LL << 60)) continue;
		dfs1(X[pos][i].first, dep + X[pos][i].second);
	}
}

void getdist(int pos) {
	for (int i = 1; i <= N; i++) dist[i] = (1LL << 60);
	dfs1(pos, 0);
}

long long solve1() {
	for (int i = 1; i <= N; i++) X[i].clear();
	for (int i = 1; i <= N - 1; i++) {
		X[A[i]].push_back(make_pair(B[i], C[i]));
		X[B[i]].push_back(make_pair(A[i], C[i]));
	}
	getdist(1);
	pair<long long, int> maxn1 = make_pair(-1, -1);
	for (int i = 1; i <= N; i++) maxn1 = max(maxn1, make_pair(dist[i], i));
	getdist(maxn1.second);
	pair<long long, int> maxn2 = make_pair(-1, -1);
	for (int i = 1; i <= N; i++) maxn2 = max(maxn2, make_pair(dist[i], i));
	return maxn2.first;
}

void solve_subtask2() {
	long long last = 0;
	for (int i = 1; i <= Q; i++) {
		D[i] = (D[i] + last) % (N - 1LL) + 1LL;
		E[i] = (E[i] + last) % W;
		C[D[i]] = E[i];
		last = solve1();
		printf("%lld\n", last);
	}
}

int cnts, cl[1 << 18], cr[1 << 18], depth[1 << 18], idx[1 << 18];
vector<int> Y[1 << 18];
LazySegmentTree Z;
set<pair<long long, int>> Set;

void dfs2(int pos, int dep) {
	depth[pos] = dep;
	cnts++; cl[pos] = cnts;
	for (int i = 0; i < X[pos].size(); i++) {
		if (cl[X[pos][i].first] >= 1) continue;
		Y[pos].push_back(X[pos][i].first);
		dfs2(X[pos][i].first, dep + 1);
	}
	cr[pos] = cnts;
}

void dfs3(int pos, int id) {
	idx[pos] = id;
	for (int i : Y[pos]) dfs3(i, id);
}

void solve_subtask5() {
	dfs2(1, 0);
	for (int i = 0; i < Y[1].size(); i++) dfs3(Y[1][i], Y[1][i]);

	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, C[i]);
	}
	for (int i = 0; i < Y[1].size(); i++) {
		long long val = Z.query(cl[Y[1][i]], cr[Y[1][i]] + 1);
		Set.insert(make_pair(val, Y[1][i]));
	}

	long long last = 0;
	for (int i = 1; i <= Q; i++) {
		D[i] = (D[i] + last) % (N - 1LL) + 1LL;
		E[i] = (E[i] + last) % W;
		long long changes = E[i] - C[D[i]];
		long long pos = B[D[i]];
		long long root = idx[B[D[i]]];
		long long val1 = Z.query(cl[root], cr[root] + 1);
		Set.erase(make_pair(val1, root));
		Z.add(cl[pos], cr[pos] + 1, changes);
		long long val2 = Z.query(cl[root], cr[root] + 1);
		Set.insert(make_pair(val2, root));

		long long r = 0; auto itr = Set.end();
		for (int t = 1; t <= 2; t++) {
			if (itr == Set.begin()) break;
			itr--;
			r += (*itr).first;
		}
		last = r; C[D[i]] = E[i];
		printf("%lld\n", r);
	}
}

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(make_pair(B[i], C[i])); 
		X[B[i]].push_back(make_pair(A[i], C[i])); 
	}
	for (int i = 1; i <= Q; i++) scanf("%lld%lld", &D[i], &E[i]);

	if (N <= 5000 && Q <= 5000) {
		solve_subtask2();
	}
	else {
		solve_subtask5();
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp:9:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
diameter.cpp: In function 'void dfs1(int, long long int)':
diameter.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'void dfs2(int, int)':
diameter.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'void solve_subtask5()':
diameter.cpp:130:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[1].size(); i++) dfs3(Y[1][i], Y[1][i]);
                  ~~^~~~~~~~~~~~~
diameter.cpp:137:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[1].size(); i++) {
                  ~~^~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:167: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:169: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:173: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: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 27