oj.uz

Submission #619259

# Submission time Handle Problem Language Result Execution time Memory
619259 2022-08-02T10:47:50 Z Zanite Dynamic Diameter (CEOI19_diameter) C++17
29 / 100
 5000 ms 37076 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("trapv")

using ll	= long long;
using pll	= pair<ll, ll>;
using Edge	= pair<ll, pll>;

#define fi	first
#define se	second

const int maxN	= 1e5 + 5;

const ll INF	= 1e18;

ll n, q, w;
set<pll> adj[maxN];
vector<Edge> edges;

ll dist[maxN], initDia[maxN], parent[maxN];
ll timer, tin[maxN], tout[maxN], byTin[maxN];

struct Segtree {
	ll sz;
	vector<ll> seg, lazy;

	Segtree(ll sz) : sz(sz) {
		seg = lazy = vector<ll>((sz << 2) + 1, 0);
	}

	void build(ll pos, ll l, ll r) {
		if (l > r) {return;}
		if (l == r) {
			seg[pos] = dist[byTin[l]];
			cerr << pos << ' ' << l << ' ' << byTin[l] << ' ' << dist[byTin[l]] << '\n';
			return;
		}

		ll m = (l+r) >> 1, lc = pos << 1, rc = lc | 1;
		build(lc, l, m);
		build(rc, m+1, r);
		seg[pos] = max(seg[lc], seg[rc]);
	}
	void build() {build(1, 1, sz);}

	void updateNode(ll pos, ll val) {
		seg[pos] += val;
		lazy[pos] += val;
	}

	void checkLazy(ll pos) {
		if (lazy[pos] != 0) {
			ll lc = pos << 1, rc = lc | 1;
			updateNode(lc, lazy[pos]);
			updateNode(rc, lazy[pos]);
			lazy[pos] = 0;
		}
	}

	void update(ll pos, ll l, ll r, ll ul, ll ur, ll val) {
		if (l > r || ul > ur || l > ur || ul > r) return;
		if (ul <= l && r <= ur) {updateNode(pos, val); return;}

		checkLazy(pos);

		ll m = (l+r) >> 1, lc = pos << 1, rc = lc | 1;
		update(lc, l, m, ul, ur, val);
		update(rc, m+1, r, ul, ur, val);
		seg[pos] = max(seg[lc], seg[rc]);
	}
	void update(ll ul, ll ur, ll val) {update(1, 1, sz, ul, ur, val);}

	ll query(ll pos, ll l, ll r, ll ul, ll ur) {
		if (l > r || ul > ur || l > ur || ul > r) return 0;
		if (ul <= l && r <= ur) return seg[pos];

		checkLazy(pos);

		ll m = (l+r) >> 1, lc = pos << 1, rc = lc | 1;
		return max(query(lc, l, m, ul, ur), query(rc, m+1, r, ul, ur));
	}
	ll query(ll ul, ll ur) {return query(1, 1, sz, ul, ur);}

	void print() {
		for (ll i = 1; i <= sz; i++) {
			cout << query(i, i) << ' ';
		}
		cout << '\n';
	}
} S(1), T(1);

void compute(ll cur) {
	ll cdist = S.query(tin[cur], tin[cur]);
	vector<ll> children(2, cdist);

	for (auto &[nxt, w] : adj[cur]) {
		children.push_back(S.query(tin[nxt], tout[nxt]));
	}
	sort(children.begin(), children.end());
	reverse(children.begin(), children.end());

	//for (auto i : children) {cout << i << ' ';} cout <<'\n';

	//cout << cur << ' ' << -T.query(cur, cur) + children[0] + children[1] - 2ll*cdist << '\n';
	T.update(cur, cur, -T.query(cur, cur) + children[0] + children[1] - 2ll*cdist);
}

#define debug(x) cout << #x << " = " << x << '\n'

void dfs(ll cur, ll par, ll cdist, ll pw) {
	//debug(cur);
	tin[cur] = ++timer;
	byTin[timer] = cur;
	parent[cur] = par;

	dist[cur] = cdist;
	S.update(tin[cur], tin[cur], cdist);

	adj[cur].erase({par, pw});

	for (auto &[nxt, w] : adj[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, cdist+w, w);
	}
	compute(cur);

	tout[cur] = timer;
}

int main() {
	scanf("%lld %lld %lld", &n, &q, &w);
	for (ll a, b, c, i = 1; i < n; i++) {
		scanf("%lld %lld %lld", &a, &b, &c);

		adj[a].insert({b, c});
		adj[b].insert({a, c});
		edges.push_back({c, {a, b}});
	}

	S = T = Segtree(n);
	dfs(1, 0, 0, 0);

	for (auto &[w, p] : edges) {
		if (tin[p.fi] > tin[p.se]) {swap(p.fi, p.se);}
	}

	//S.print(); T.print();
	/*
	for (ll i = 1; i <= n; i++) {
		cout << i << ": ";
		for (auto &[j, k] : adj[i]) {
			cout << "{" << j << ", " << k << "} ";
		}
		cout << '\n';
	}
	*/

	ll last = 0;

	for (ll d, e, i = 1; i <= q; i++) {
		scanf("%lld %lld", &d, &e);
		d = (d + last) % (n - 1);
		e = (e + last) % w;

		//debug(d); debug(e);

		auto &[w, p] = edges[d];
		//debug(e-w);

		S.update(tin[p.se], tout[p.se], e-w);

		adj[p.fi].erase({p.se, w});

		edges[d].fi = e;
		adj[p.fi].insert({p.se, e});

		for (ll cur = p.fi; cur > 0; cur = parent[cur]) {
			//debug(cur);
			compute(cur);
		}
		//S.print(); T.print();

		last = T.query(1, n);
		printf("%lld\n", last);
	}
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |  scanf("%lld %lld %lld", &n, &q, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   scanf("%lld %lld %lld", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |   scanf("%lld %lld", &d, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4932 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 5 ms 5056 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4932 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 5 ms 5056 KB Output is correct
19 Correct 126 ms 5340 KB Output is correct
20 Correct 195 ms 5332 KB Output is correct
21 Correct 573 ms 5472 KB Output is correct
22 Correct 1234 ms 5408 KB Output is correct
23 Correct 223 ms 6600 KB Output is correct
24 Correct 704 ms 6780 KB Output is correct
25 Correct 2344 ms 6836 KB Output is correct
26 Execution timed out 5047 ms 7272 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 8 ms 4948 KB Output is correct
4 Correct 62 ms 5000 KB Output is correct
5 Correct 298 ms 5448 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 8 ms 5076 KB Output is correct
8 Correct 24 ms 5192 KB Output is correct
9 Correct 205 ms 5176 KB Output is correct
10 Correct 2060 ms 5232 KB Output is correct
11 Execution timed out 5092 ms 5408 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5332 KB Output is correct
2 Correct 74 ms 5360 KB Output is correct
3 Correct 385 ms 5488 KB Output is correct
4 Correct 710 ms 5888 KB Output is correct
5 Correct 32 ms 8080 KB Output is correct
6 Correct 170 ms 8264 KB Output is correct
7 Correct 600 ms 8612 KB Output is correct
8 Correct 1256 ms 9100 KB Output is correct
9 Correct 129 ms 20832 KB Output is correct
10 Correct 280 ms 21144 KB Output is correct
11 Correct 937 ms 21292 KB Output is correct
12 Correct 1812 ms 21216 KB Output is correct
13 Correct 257 ms 36216 KB Output is correct
14 Correct 433 ms 36488 KB Output is correct
15 Correct 1201 ms 36756 KB Output is correct
16 Correct 2139 ms 37076 KB Output is correct
17 Correct 3676 ms 36968 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5094 ms 36572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4932 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 5 ms 5056 KB Output is correct
19 Correct 126 ms 5340 KB Output is correct
20 Correct 195 ms 5332 KB Output is correct
21 Correct 573 ms 5472 KB Output is correct
22 Correct 1234 ms 5408 KB Output is correct
23 Correct 223 ms 6600 KB Output is correct
24 Correct 704 ms 6780 KB Output is correct
25 Correct 2344 ms 6836 KB Output is correct
26 Execution timed out 5047 ms 7272 KB Time limit exceeded
27 Halted 0 ms 0 KB -