답안 #922378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922378	2024-02-05T12:56:53 Z	SNP011	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	499 ms	59592 KB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define pb push_back
const int maxn = 2e5 + 5;

int h[maxn], dp[5][4 * maxn], lastans;
int lazy[4 * maxn], st[maxn], fn[maxn];
vector<pii> adj[maxn];
vector<int> discovery;
map<pii, int> we;

void dfs(int v, int par = 0) {
	st[v] = discovery.size();
	discovery.pb(h[v]);
	for (auto[w, u]: adj[v]) {
		if (u != par) {
			h[u] = h[v] + w;
			dfs(u, v);
			discovery.pb(h[v]);
		}
	}
	fn[v] = discovery.size() - 1;
}

void updateDP(int id, int L, int R) {
	if (R - L >= 2) {
		dp[3][id] = max({dp[3][2 * id], dp[3][2 * id + 1], dp[2][2 * id] - (2 * dp[1][2 * id + 1])});
		dp[4][id] = max({dp[4][2 * id], dp[4][2 * id + 1], dp[2][2 * id + 1] - (2 * dp[1][2 * id])});
	}
	if (R - L >= 3) {
		dp[0][id] = max({dp[0][2 * id], dp[0][2 * id + 1], dp[2][2 * id] + dp[4][2 * id + 1], dp[3][2 * id] + dp[2][2 * id + 1]});
	}
	dp[1][id] = min(dp[1][2 * id], dp[1][2 * id + 1]);
	dp[2][id] = max(dp[2][2 * id], dp[2][2 * id + 1]);
}

struct segment {
	void init(int id, int L, int R) {
		if (L + 1 == R) {
			if (discovery.size() >= L) {
				dp[1][id] = discovery[L];
				dp[2][id] = discovery[L];
			}
			return;
		}
		int mid = (R + L) >> 1;
		init(2 * id, L, mid);
		init(2 * id + 1, mid, R);
		updateDP(id, L, R);
	}

	void spread(int id, int L, int R) {
		int mid = (R + L) >> 1;

		dp[1][2 * id] += lazy[id];
		dp[2][2 * id] += lazy[id];
		if (mid - L >= 2) {
			dp[3][2 * id] -= lazy[id];
			dp[4][2 * id] -= lazy[id];
		}

		dp[1][2 * id + 1] += lazy[id];
		dp[2][2 * id + 1] += lazy[id];
		if (R - mid >= 2) {
			dp[3][2 * id + 1] -= lazy[id];
			dp[4][2 * id + 1] -= lazy[id];
		}

		lazy[2 * id] += lazy[id];
		lazy[2 * id + 1] += lazy[id];
		lazy[id] = 0;
	}

	void update(int id, int L, int R, int l, int r, int val) {
		if (L == l and R == r) {
			dp[1][id] += val;
			dp[2][id] += val;
			if (R - L >= 2) {
				dp[3][id] -= val;
				dp[4][id] -= val;	
			}
			lazy[id] += val;
			return;
		}
		spread(id, L, R);
		int mid = (R + L) >> 1;
		if (l < mid) {
			update(2 * id, L, mid, l, min(r, mid), val);
		}
		if (r > mid) {
			update(2 * id + 1, mid, R, max(l, mid), r, val);
		}
		updateDP(id, L, R);
	}
} seg;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q, w;
	cin >> n >> q >> w;
	vector<pii> edge;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[v].pb({w, u});
		adj[u].pb({w, v});
		we[{u, v}] = w;
		we[{v, u}] = w;
		edge.pb({u, v});
	}
	discovery.pb(-1);
	dfs(1);
	seg.init(1, 1, maxn);
	while (q--) {
		int d, e;
		cin >> d >> e;
		d = (d + lastans) % (n - 1);
		e = (e + lastans) % w;
		// cout << d << ", " << e << ": ";
		int u = edge[d].first, v = edge[d].second;
		if (h[u] < h[v]) {
			swap(u, v);
		} // h[u] >= h[v]
		seg.update(1, 1, maxn, st[u], fn[u] + 1, e - we[edge[d]]);
		// cout << e - we[{edge[d]}] << "->" << st[u] << ", " << fn[u] << '\n';
		we[{u, v}] = e;
		we[{v, u}] = e;
		lastans = dp[0][1];
		cout << dp[0][1] << '\n';
	}
	return 0;
}

Compilation message

diameter.cpp: In member function 'void segment::init(long long int, long long int, long long int)':
diameter.cpp:44:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |    if (discovery.size() >= L) {
      |        ~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	9 ms	27736 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	9 ms	27736 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	27736 KB	Output is correct
2	Correct	8 ms	27736 KB	Output is correct
3	Correct	9 ms	27992 KB	Output is correct
4	Correct	17 ms	27832 KB	Output is correct
5	Correct	52 ms	27984 KB	Output is correct
6	Correct	9 ms	27740 KB	Output is correct
7	Correct	8 ms	27740 KB	Output is correct
8	Correct	9 ms	27736 KB	Output is correct
9	Correct	10 ms	27736 KB	Output is correct
10	Correct	24 ms	28252 KB	Output is correct
11	Correct	82 ms	28260 KB	Output is correct
12	Correct	11 ms	29016 KB	Output is correct
13	Correct	12 ms	29020 KB	Output is correct
14	Correct	13 ms	29020 KB	Output is correct
15	Correct	28 ms	29020 KB	Output is correct
16	Correct	82 ms	29372 KB	Output is correct
17	Correct	106 ms	57060 KB	Output is correct
18	Correct	85 ms	57012 KB	Output is correct
19	Correct	86 ms	57000 KB	Output is correct
20	Correct	118 ms	57344 KB	Output is correct
21	Correct	337 ms	57844 KB	Output is correct