oj.uz

Submission #926057

# Submission time Handle Problem Language Result Execution time Memory
926057 2024-02-12T13:59:31 Z SNP011 Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
 628 ms 1048576 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define pii pair<long long, long long>
#define int long long
const int maxn = 2e5 + 5, inf = 1e18;
 
int lastans;
int n, q, w;
vector<pii> adj[maxn], edge;
map<pii, int> va;
vector<int> dis;
bool vis[maxn];
int dp[4 * maxn][5], st[maxn], fn[maxn];
int h[maxn], lazy[4 * maxn], _h[maxn];
 
void dfs(int v) {
	vis[v] = 1;
	st[v] = dis.size();
	dis.pb(h[v]);
	for (auto[w, u]: adj[v]) {
		if (!vis[u]) {
			_h[u] = _h[v] + 1;
			h[u] = h[v] + w;
			dfs(u);
			dis.pb(h[v]);
		}
	}
	fn[v] = dis.size() - 1;
}
 
void updateDP(int id) {
	int lc = 2 * id, rc = 2 * id + 1;
	dp[id][0] = max({dp[lc][0], dp[rc][0], dp[lc][2] + dp[rc][4], dp[lc][3] + dp[rc][2]});
	dp[id][1] = min(dp[lc][1], dp[rc][1]);
	dp[id][2] = max(dp[lc][2], dp[rc][2]);
	dp[id][3] = max({dp[lc][3], dp[rc][3], dp[lc][2] - (2 * dp[rc][1])});
	dp[id][4] = max({dp[lc][4], dp[rc][4], dp[rc][2] - (2 * dp[lc][1])});
}
 
void printDP(int id, int L, int R) {
	cout << L << ", " << R - 1 << ": \n";
	cout << "dp[0] = " << dp[id][0] << '\n';
	cout << "dp[1] = " << dp[id][1] << '\n';
	cout << "dp[2] = " << dp[id][2] << '\n';
	cout << "dp[3] = " << dp[id][3] << '\n';
	cout << "dp[4] = " << dp[id][4] << '\n';
	cout << "\n\n-----------------\n\n";
}
 
struct segment {
	void spread(int id) {
		dp[2 * id][1] += lazy[id];
		dp[2 * id][2] += lazy[id];
		dp[2 * id][3] -= lazy[id];
		dp[2 * id][4] -= lazy[id];
 
		dp[2 * id + 1][1] += lazy[id];
		dp[2 * id + 1][2] += lazy[id];
		dp[2 * id + 1][3] -= lazy[id];
		dp[2 * id + 1][4] -= lazy[id];
 
		lazy[2 * id] += lazy[id];
		lazy[2 * id + 1] += lazy[id];
		lazy[id] = 0;
	}
 
	void init(int id, int L, int R) {
		if (L + 1 == R) {
			dp[id][1] = dis[L];
			dp[id][2] = dis[L];
			// printDP(id, L, R);
			return;
		}
		int mid = (R + L) >> 1;
		init(2 * id, L, mid);
		init(2 * id + 1, mid, R);
		updateDP(id);
		// printDP(id, L, R);
	}
 
	void update(int id, int L, int R, int l, int r, int val) {
		if (L == l and R == r) {
			dp[id][1] += val;
			dp[id][2] += val;
			dp[id][3] -= val;
			dp[id][4] -= val;
			lazy[id] += val;
			return;
		}
		spread(id);
		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);
		// printDP(id, L, R);
	}
} seg;
 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  	freopen("inp.txt", "r", stdin);
 	freopen("wrong.txt", "w", stdout);
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j < 5; j++) {
			dp[i][j] = (j == 1 ? inf : 0 - inf);
		}
	}
 
	cin >> n >> q >> w;
	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});
		va[{u, v}] = _w;
		va[{v, u}] = _w;
		edge.pb({u, v});
	}
	dis.pb(-1);
	dfs(1);
	seg.init(1, 1, 2 * n);
	while (q--) {
		int i, x;
		cin >> i >> x;
		// i = (i + lastans) % (n - 1);
		// x = (x + lastans) % w;
		int u = edge[i].first, v = edge[i].second;
 
		if (_h[u] < _h[v]) {
			swap(u, v);
		} // h[u] > h[v]
		seg.update(1, 1, 2 * n, st[u], fn[u] + 1, x - va[{u, v}]);
		cout << max(dp[1][0], dp[1][2]) << '\n';
		lastans = max(dp[1][0], dp[1][2]);
		va[{u, v}] = x;
		va[{v, u}] = x;
	}
	return 0;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:110:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |    freopen("inp.txt", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:111:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen("wrong.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 571 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 555 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 552 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -