Submission #1094233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094233		hvmegy	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	425 ms	95828 KiB

diameter

// [ нvмegy ]
// OLPSIEUCUP AND ICPC 2024 GOTOHANOI

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int long long
 
#define all(c) c.begin(), c.end()
#ifdef hvmegy
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
	cerr << "[" << vars << " : ";
	string delim = "";
	(..., (cerr << delim << values, delim = ", "));
	cerr << "]" << '\n'; 
}
#else
#define dbg(...)
#endif
 
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
 
int GOTOHANOI();
void init(); 
 
int32_t main()
{
        cin.tie(0) -> sync_with_stdio(0); 
        cout << fixed << setprecision(15);
	
	#ifdef hvmegy
	freopen("input.txt", "r", stdin); 
	freopen("output.txt", "w", stdout); 
	freopen("log.txt", "w", stderr);
	#endif



	// =============================
        	bool MULTITEST = 0; 
	// =============================
	
	init(); 
        int OLPSIEUCUP2024 = 1; 
        if (MULTITEST) cin >> OLPSIEUCUP2024; 
	for (int i = 1; i <= OLPSIEUCUP2024; i++) {
		if (GOTOHANOI()) break;
		#ifdef hvmegy
			cout << "--ENDTEST--" << '\n';
			cerr << "--ENDTEST--" << '\n';
		#endif
	}

	#ifdef hvmegy
		cerr << '\n' << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << '\n';
	#endif

        return 0;
}

void init() {}

struct info { 
	int dp[3][3]; 
	bool empty = 1; 
	info() { 
		empty = 1; 
	}
	info(int val) { 
		int vec[3]; 
		vec[0] = val; 
		vec[1] = -2 * val; 
		vec[2] = val; 
		for (int i = 0; i < 3; i++) { 
			int sum = 0; 
			for (int j = i; j < 3; j++) { 
				sum += vec[j]; 
				dp[i][j] = sum; 
			}
		}
		empty = 0; 
	}
	void apply(int val) { 
		int vec[3]; 
		vec[0] = val; 
		vec[1] = -2 * val; 
		vec[2] = val; 
		for (int i = 0; i < 3; i++) { 
			int sum = 0; 
			for (int j = i; j < 3; j++) { 
				sum += vec[j]; 
				dp[i][j] += sum; 
			}
		}
	}
}; 

info operator + (info lef, info rig) { 
	if (lef.empty || rig.empty) { 
		return lef.empty ? rig : lef; 
	}
	info res; 
	res.empty = 0; 
	for (int i = 0; i < 3; i++) { 
		for (int j = i; j < 3; j++) { 
			res.dp[i][j] = max(lef.dp[i][j], rig.dp[i][j]); 
		}
	}
	for (int i = 0; i < 3; i++) { 
		for (int j = i; j < 3; j++) { 
			for (int k = i; k < j; k++) { 
				res.dp[i][j] = max(res.dp[i][j], lef.dp[i][k] + rig.dp[k + 1][j]); 
			}
		}
	}
	return res; 

}

struct Segtree { 
	vector<info> st; 
	vector<int> lz; 
	int n; 
#define lc id << 1 
#define rc id << 1 | 1
#define mi ((l + r) >> 1)
	Segtree(int n, int * a): n(n), st(4 * n), lz(4 * n) { 
		auto build = [&](auto && f, int id, int l, int r) -> void { 
			if (l == r) { 
				st[id] = info(a[l]); 
				dbg(st[id].dp[0][0]); 
				return; 
			}
			f(f, lc, l, mi); 
			f(f, rc, mi+1, r); 
			st[id] = st[lc] + st[rc]; 
			return; 
		};
		build(build, 1, 1, n); 
	}

	void push(int id, int l, int r) { 
		if (lz[id]) { 
			int x = lz[id]; 
			lz[id] = 0; 
			update(l, mi, x, lc, l, mi); 
			update(mi+1, r, x, rc, mi+1, r); 
		}
	}
	void update(int u, int v, int x, int id, int l, int r) { 
		dbg(u, v, x, id, l, r); 
		if (u > r || l > v) { 
			return; 
		}
		if (u <= l && r <= v) { 
			dbg(u, v, x); 
			st[id].apply(x); 
			lz[id] += x; 
			return; 
		}
		push(id, l, r); 
		update(u, v, x, lc, l, mi); 
		update(u, v, x, rc, mi+1, r); 
		st[id] = st[lc] + st[rc]; 
	}
};

int const N = 1e5; 
int n, m, mxW; 
int in[N + 1], out[N + 1]; 
int seq[2 * N]; 
int dis[N + 1], dep[N + 1]; 
vector<pair<int, int>> adj[N + 1]; 
tuple<int, int, int> ed[N + 1]; 

int et = 0; 
void dfs(int u, int p) { 
	in[u] = ++et; 
	seq[in[u]] = dis[u]; 
	for (auto [v, w] : adj[u]) { 
		if (v == p) continue; 
		dep[v] = dep[u] + 1; 
		dis[v] = dis[u] + w; 
		dfs(v, u); 
	}
	out[u] = et; 
	if (u != 1) { 
		++et; 
		seq[et] = dis[p]; 
	}
}

int GOTOHANOI() { 
	cin >> n >> m >> mxW; 
	for (int i = 1; i < n; i++) { 
		int u, v, w; 
		cin >> u >> v >> w; 
		ed[i] = {u, v, w}; 
		adj[u].push_back({v, w}); 
		adj[v].push_back({u, w}); 
	}

	dfs(1, 1); 
	Segtree ST(et, seq); 

	int last = 0; 
	while (m--) { 
		int d, e; 
		cin >> d >> e; 
		d = (d + last) % (n - 1); 
		e = (e + last) % mxW; 
		auto & [u, v, w] = ed[d + 1]; 
		if (dep[u] > dep[v]) swap(u, v); 
		ST.update(in[v], out[v], e - w, 1, 1, et); 
		last = ST.st[1].dp[0][2]; 
		cout << last << '\n';
		w = e; 
	}
	
	
	
	return 0; 
}

Compilation message (stderr)

diameter.cpp: In constructor 'Segtree::Segtree(long long int, long long int*)':
diameter.cpp:125:6: warning: 'Segtree::n' will be initialized after [-Wreorder]
  125 |  int n;
      |      ^
diameter.cpp:123:15: warning:   'std::vector<info> Segtree::st' [-Wreorder]
  123 |  vector<info> st;
      |               ^~
diameter.cpp:129:2: warning:   when initialized here [-Wreorder]
  129 |  Segtree(int n, int * a): n(n), st(4 * n), lz(4 * n) {
      |  ^~~~~~~

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