oj.uz

답안 #680085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680085 2023-01-09T21:40:45 Z SanguineChameleon Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 2469 ms 165328 KB 
// BEGIN BOILERPLATE CODE

#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

long double rand_real(long double rmin, long double rmax) {
	uniform_real_distribution<long double> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const int ms = 1e5 + 20;

struct range {
	int root = 0;
	int pos = 0;
	int lt = 0;
	int rt = 0;

	range() {

	}

	range(int _root, int _pos, int _lt, int _rt) {
		root = _root;
		pos = _pos;
		lt = _lt;
		rt = _rt;
	}
};

long long a[ms];

struct tree {
	vector<long long> tr;
	vector<long long> lz;
	int n = 0;

	void build(int cc, int lt, int rt) {
		if (lt == rt) {
			tr[cc] = a[lt];
			return;
		}
		int mt = (lt + rt) / 2;
		build(cc << 1, lt, mt);
		build(cc << 1 | 1, mt + 1, rt);
		tr[cc] = max(tr[cc << 1], tr[cc << 1 | 1]);
	}

	tree() {

	}

	tree(int _n) {
		n = _n;
		tr.resize(n << 2);
		lz.resize(n << 2);
		build(1, 1, n);
	}

	void push(int cc) {
		tr[cc << 1] += lz[cc];
		lz[cc << 1] += lz[cc];
		tr[cc << 1 | 1] += lz[cc];
		lz[cc << 1 | 1] += lz[cc];
		lz[cc] = 0;
	}

	void update(int cc, int lt, int rt, int ql, int qr, long long pp) {
		if (lt == ql && rt == qr) {
			tr[cc] += pp;
			lz[cc] += pp;
			return;
		}
		push(cc);
		int mt = (lt + rt) / 2;
		if (qr <= mt) {
			update(cc << 1, lt, mt, ql, qr, pp);
		}
		else if (ql >= mt + 1) {
			update(cc << 1 | 1, mt + 1, rt, ql, qr, pp);
		}
		else {
			update(cc << 1, lt, mt, ql, mt, pp);
			update(cc << 1 | 1, mt + 1, rt, mt + 1, qr, pp);
		}
		tr[cc] = max(tr[cc << 1], tr[cc << 1 | 1]);
	}
};

bool f[ms];
int sz[ms];
long long W[ms];
vector<pair<int, int>> adj[ms];
int pt[ms][2];
int tz;
multiset<long long, greater<long long>> S;
multiset<long long, greater<long long>> best[ms];
vector<range> R[ms];
vector<tree> T[ms];

void dfs1(int u, int pr) {
	sz[u] = 1;
	for (auto x: adj[u]) {
		int v = x.first;
		if (!f[v] && v != pr) {
			dfs1(v, u);
			sz[u] += sz[v];
		}
	}
}

int ctr(int u, int pr, int root) {
	for (auto x: adj[u]) {
		int v = x.first;
		if (!f[v] && v != pr) {
			if (sz[v] * 2 > sz[root]) {
				return ctr(v, u, root);
			}
		}
	}
	return u;
}

void dfs2(int u, int pr, int root, int pos, long long cur) {
	tz++;
	pt[u][0] = tz;
	a[tz] = cur;
	sz[u] = 1;
	for (auto x: adj[u]) {
		int v = x.first;
		int id = x.second;
		if (!f[v] && v != pr) {
			dfs2(v, u, root, pos, cur + W[id]);
			R[id].emplace_back(root, pos, pt[v][0], pt[v][1]);
			sz[u] += sz[v];
		}
	}
	pt[u][1] = tz;
}


long long get(int u) {
	long long res = 0;
	auto it = best[u].begin();
	if (it == best[u].end()) {
		return res;
	}
	res += (*it);
	it++;
	if (it == best[u].end()) {
		return res;
	}
	res += (*it);
	return res;
}

void build(int u) {
	dfs1(u, -1);
	u = ctr(u, -1, u);
	f[u] = true;
	int cnt = 0;
	for (auto x: adj[u]) {
		int v = x.first;
		int id = x.second;
		if (!f[v]) {
			tz = 0;
			dfs2(v, -1, u, cnt, W[id]);
			R[id].emplace_back(u, cnt, pt[v][0], pt[v][1]);
			T[u].emplace_back(sz[v]);
			best[u].insert(T[u][cnt].tr[1]);
			cnt++;
		}
	}
	S.insert(get(u));
	for (auto x: adj[u]) {
		int v = x.first;
		if (!f[v]) {
			build(v);
		}
	}
}

void update(range r, long long pp) {
	int root = r.root;
	int pos = r.pos;
	int lt = r.lt;
	int rt = r.rt;
	S.erase(S.find(get(root)));
	tree &t = T[root][pos];
	best[root].erase(best[root].find(t.tr[1]));
	t.update(1, 1, t.n, lt, rt, pp);
	best[root].insert(t.tr[1]);
	S.insert(get(root));
}


void just_do_it() {
	int n, q;
	long long lim;
	cin >> n >> q >> lim;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v >> W[i];
		adj[u].emplace_back(v, i);
		adj[v].emplace_back(u, i);
	}
	build(1);
	long long res = 0;
	for (int i = 0; i < q; i++) {
		int id;
		long long w;
		cin >> id >> w;
		id = (res + id) % (n - 1);
		w = (res + w) % lim;
		for (auto r: R[id]) {
			update(r, w - W[id]);
		}
		W[id] = w;
		res = *S.begin();
		cout << res << '\n';
	}
}

// END MAIN CODE

Compilation message

diameter.cpp: In function 'void file_io(std::string, std::string)':
diameter.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 8 ms 12100 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12060 KB Output is correct
9 Correct 6 ms 12052 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 6 ms 12040 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 6 ms 12116 KB Output is correct
17 Correct 6 ms 12064 KB Output is correct
18 Correct 6 ms 12116 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 8 ms 12100 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12060 KB Output is correct
9 Correct 6 ms 12052 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 6 ms 12040 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 6 ms 12116 KB Output is correct
17 Correct 6 ms 12064 KB Output is correct
18 Correct 6 ms 12116 KB Output is correct
19 Correct 17 ms 12812 KB Output is correct
20 Correct 19 ms 12756 KB Output is correct
21 Correct 20 ms 12920 KB Output is correct
22 Correct 21 ms 13132 KB Output is correct
23 Correct 31 ms 15828 KB Output is correct
24 Correct 35 ms 16776 KB Output is correct
25 Correct 40 ms 17376 KB Output is correct
26 Correct 43 ms 18252 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 13 ms 12116 KB Output is correct
5 Correct 42 ms 12432 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 12240 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 8 ms 12220 KB Output is correct
10 Correct 15 ms 12328 KB Output is correct
11 Correct 49 ms 12628 KB Output is correct
12 Correct 12 ms 13680 KB Output is correct
13 Correct 11 ms 13700 KB Output is correct
14 Correct 12 ms 13680 KB Output is correct
15 Correct 22 ms 13808 KB Output is correct
16 Correct 64 ms 14176 KB Output is correct
17 Correct 131 ms 45432 KB Output is correct
18 Correct 130 ms 45376 KB Output is correct
19 Correct 137 ms 45460 KB Output is correct
20 Correct 161 ms 45564 KB Output is correct
21 Correct 308 ms 45952 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12944 KB Output is correct
2 Correct 26 ms 12884 KB Output is correct
3 Correct 91 ms 13120 KB Output is correct
4 Correct 168 ms 13384 KB Output is correct
5 Correct 30 ms 23628 KB Output is correct
6 Correct 58 ms 23740 KB Output is correct
7 Correct 211 ms 23952 KB Output is correct
8 Correct 317 ms 24300 KB Output is correct
9 Correct 137 ms 78028 KB Output is correct
10 Correct 181 ms 78080 KB Output is correct
11 Correct 399 ms 78416 KB Output is correct
12 Correct 788 ms 78732 KB Output is correct
13 Correct 299 ms 150452 KB Output is correct
14 Correct 334 ms 150604 KB Output is correct
15 Correct 640 ms 150760 KB Output is correct
16 Correct 1089 ms 151348 KB Output is correct
17 Correct 2134 ms 151196 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1609 ms 125428 KB Output is correct
2 Correct 1662 ms 128704 KB Output is correct
3 Correct 1670 ms 127916 KB Output is correct
4 Correct 1706 ms 128448 KB Output is correct
5 Correct 1622 ms 122372 KB Output is correct
6 Correct 1440 ms 89520 KB Output is correct
7 Correct 2257 ms 153616 KB Output is correct
8 Correct 2359 ms 153676 KB Output is correct
9 Correct 2203 ms 153792 KB Output is correct
10 Correct 2231 ms 153016 KB Output is correct
11 Correct 2268 ms 145616 KB Output is correct
12 Correct 2001 ms 103560 KB Output is correct
13 Correct 2416 ms 165320 KB Output is correct
14 Correct 2462 ms 165248 KB Output is correct
15 Correct 2406 ms 165328 KB Output is correct
16 Correct 2409 ms 164588 KB Output is correct
17 Correct 2371 ms 155744 KB Output is correct
18 Correct 1888 ms 107844 KB Output is correct
19 Correct 2364 ms 165308 KB Output is correct
20 Correct 2322 ms 165252 KB Output is correct
21 Correct 2469 ms 165312 KB Output is correct
22 Correct 2261 ms 164504 KB Output is correct
23 Correct 2171 ms 155728 KB Output is correct
24 Correct 1804 ms 107768 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 8 ms 12100 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12060 KB Output is correct
9 Correct 6 ms 12052 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 6 ms 12116 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 6 ms 12040 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 6 ms 12116 KB Output is correct
17 Correct 6 ms 12064 KB Output is correct
18 Correct 6 ms 12116 KB Output is correct
19 Correct 17 ms 12812 KB Output is correct
20 Correct 19 ms 12756 KB Output is correct
21 Correct 20 ms 12920 KB Output is correct
22 Correct 21 ms 13132 KB Output is correct
23 Correct 31 ms 15828 KB Output is correct
24 Correct 35 ms 16776 KB Output is correct
25 Correct 40 ms 17376 KB Output is correct
26 Correct 43 ms 18252 KB Output is correct
27 Correct 7 ms 11988 KB Output is correct
28 Correct 6 ms 11988 KB Output is correct
29 Correct 7 ms 12116 KB Output is correct
30 Correct 13 ms 12116 KB Output is correct
31 Correct 42 ms 12432 KB Output is correct
32 Correct 6 ms 11988 KB Output is correct
33 Correct 7 ms 12240 KB Output is correct
34 Correct 7 ms 12244 KB Output is correct
35 Correct 8 ms 12220 KB Output is correct
36 Correct 15 ms 12328 KB Output is correct
37 Correct 49 ms 12628 KB Output is correct
38 Correct 12 ms 13680 KB Output is correct
39 Correct 11 ms 13700 KB Output is correct
40 Correct 12 ms 13680 KB Output is correct
41 Correct 22 ms 13808 KB Output is correct
42 Correct 64 ms 14176 KB Output is correct
43 Correct 131 ms 45432 KB Output is correct
44 Correct 130 ms 45376 KB Output is correct
45 Correct 137 ms 45460 KB Output is correct
46 Correct 161 ms 45564 KB Output is correct
47 Correct 308 ms 45952 KB Output is correct
48 Correct 9 ms 12944 KB Output is correct
49 Correct 26 ms 12884 KB Output is correct
50 Correct 91 ms 13120 KB Output is correct
51 Correct 168 ms 13384 KB Output is correct
52 Correct 30 ms 23628 KB Output is correct
53 Correct 58 ms 23740 KB Output is correct
54 Correct 211 ms 23952 KB Output is correct
55 Correct 317 ms 24300 KB Output is correct
56 Correct 137 ms 78028 KB Output is correct
57 Correct 181 ms 78080 KB Output is correct
58 Correct 399 ms 78416 KB Output is correct
59 Correct 788 ms 78732 KB Output is correct
60 Correct 299 ms 150452 KB Output is correct
61 Correct 334 ms 150604 KB Output is correct
62 Correct 640 ms 150760 KB Output is correct
63 Correct 1089 ms 151348 KB Output is correct
64 Correct 2134 ms 151196 KB Output is correct
65 Correct 1609 ms 125428 KB Output is correct
66 Correct 1662 ms 128704 KB Output is correct
67 Correct 1670 ms 127916 KB Output is correct
68 Correct 1706 ms 128448 KB Output is correct
69 Correct 1622 ms 122372 KB Output is correct
70 Correct 1440 ms 89520 KB Output is correct
71 Correct 2257 ms 153616 KB Output is correct
72 Correct 2359 ms 153676 KB Output is correct
73 Correct 2203 ms 153792 KB Output is correct
74 Correct 2231 ms 153016 KB Output is correct
75 Correct 2268 ms 145616 KB Output is correct
76 Correct 2001 ms 103560 KB Output is correct
77 Correct 2416 ms 165320 KB Output is correct
78 Correct 2462 ms 165248 KB Output is correct
79 Correct 2406 ms 165328 KB Output is correct
80 Correct 2409 ms 164588 KB Output is correct
81 Correct 2371 ms 155744 KB Output is correct
82 Correct 1888 ms 107844 KB Output is correct
83 Correct 2364 ms 165308 KB Output is correct
84 Correct 2322 ms 165252 KB Output is correct
85 Correct 2469 ms 165312 KB Output is correct
86 Correct 2261 ms 164504 KB Output is correct
87 Correct 2171 ms 155728 KB Output is correct
88 Correct 1804 ms 107768 KB Output is correct
89 Correct 1597 ms 126660 KB Output is correct
90 Correct 1792 ms 137548 KB Output is correct
91 Correct 2073 ms 150104 KB Output is correct
92 Correct 2178 ms 153548 KB Output is correct
93 Correct 2319 ms 158040 KB Output is correct
94 Correct 2265 ms 160376 KB Output is correct
95 Correct 2272 ms 162860 KB Output is correct
96 Correct 2282 ms 162908 KB Output is correct
97 Correct 2308 ms 162764 KB Output is correct
98 Correct 2339 ms 165180 KB Output is correct
99 Correct 2277 ms 162940 KB Output is correct
100 Correct 2279 ms 162732 KB Output is correct