oj.uz

답안 #249941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249941 2020-07-16T14:10:29 Z mieszko11b Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 1288 ms 37624 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;

struct SegmentSegmentTree {
	int lv;
	vector<pll> d;
	vector<ll> ins;
	
	//1..n
	SegmentSegmentTree(int n) {
		lv = 2;
		while(lv < n + 2)
			lv *= 2;
		d.resize(2 * lv + 3, {-1e18, 0});
		ins.resize(2 * lv + 3);
		for(int i = 1 ; i <= lv ; i++)
			d[lv + i - 1].Y = i;
	}
	
	void initv(int i, ll x) {
		d[lv + i - 1].X = x;
	}
	
	void process_init() {
		for(int i = lv - 1 ; i >= 1 ; i--)
			d[i] = max(d[2 * i], d[2 * i + 1]);
	}
	
	void insert(int a, int b, int l, int r, int w, ll x) {
		if(a > r || b < l || l > r)
			return ;
		if(a <= l && r <= b) {
			ins[w] += x;
			d[w].X += x;
			return; 
		}
		
		insert(a, b, l, (l + r) / 2, 2 * w, x);
		insert(a, b, (l + r) / 2 + 1, r, 2 * w + 1, x);
		d[w] = max(d[2 * w], d[2 * w + 1]);
		d[w].X += ins[w];
	}
	
	void insert(int a, int b, ll x) {
		insert(a, b, 1, lv, 1, x);
	}
	
	pll query(int a, int b, int l, int r, int w) {
		if(a > r || b < l || l > r)
			return {-1e18, 0};
		if(a <= l && r <= b)
			return d[w];
		
		pll p1 = query(a, b, l, (l + r) / 2, 2 * w);
		pll p2 = query(a, b, (l + r) / 2 + 1, r, 2 * w + 1);
		p1 = max(p1, p2);
		p1.X += ins[w];
		return p1;
	}
	
	pll query(int a, int b) {
		return query(a, b, 1, lv, 1);
	}
};

int n, q;
ll w;
vector<pll> G[100007];
ii E[100007];
ll ecost[100007];
int p[100007], sz[100007];
int in[100007], out[100007];
int rein[100007];
int nxt_num = 1;
int first[100007];
SegmentSegmentTree paths(100007);
SegmentSegmentTree subtrees(100007);

void dfs(int w) {
	sz[w] = 1;
	for(auto u : G[w]) {
		if(u.X != p[w]) {
			p[u.X] = w;
			dfs(u.X);
			sz[w] += sz[u.X];
		}
	}
}

ll dfs2(int w, ll dist) {
	for(auto &u : G[w])
		if(sz[u.X] > sz[G[w][0].X])	
			swap(u, G[w][0]);
			
	in[w] = out[w] = nxt_num++;
	rein[in[w]] = w;
	
	subtrees.initv(in[w], dist);

	ll maxdist = dist;
	for(auto u : G[w]) {
		if(u == G[w][0])
			first[u.X] = first[w];
		else
			first[u.X] = u.X;
		if(u != G[w][0])
			maxdist = max(maxdist, dfs2(u.X, dist + u.Y));
		else
			dfs2(u.X, dist + u.Y);
		out[w] = out[u.X];
	}
	
	paths.initv(in[w], maxdist - 2LL * dist);
	
	return maxdist;
}

ll longest_path() {
	auto q = subtrees.query(1, n);
	int w = rein[q.Y], pre = 0;
	ll dw = q.X;

	//~ cout << dw << " " << w << endl;

	ll res = 0;
	while(w) {
		if(!pre || first[pre] == first[w]) {
			res = max(res, paths.query(in[first[w]], in[w]).X + dw);
			//~ cout << in[first[w]] << " " << in[w] << " " << w << " " << res << " " << paths.query(in[first[w]], in[w]).Y << endl;
			pre = first[w];
			w = p[first[w]];
		} else {
			ll pdist = subtrees.query(in[w], in[w]).X;
			res = max(res, subtrees.query(in[w], in[pre] - 1).X + dw - 2LL * pdist);
									//~ cout << w << " " << pre << " " << pdist << " " << dw << " " << res << endl;
			res = max(res, subtrees.query(out[pre] + 1, out[w]).X + dw - 2LL * pdist);
						//~ cout << w << " " << pre << " " << pdist << " " << dw << " " << res << endl;
			pre = w;
			w = p[w];
		}
	}
	
	
	return res;
}

void change_edge(int e, ll x) {
	//~ cout << e << " " << x << endl;
	
	int w = E[e].X;
	int u = E[e].Y;
	if(in[w] > in[u])
		swap(w, u);
		
	ll delta = x - ecost[e];
	ecost[e] = x;
		
	paths.insert(in[u], out[u], -delta);
	subtrees.insert(in[u], out[u], delta);
	
	w = p[first[u]];
	
	//~ cout << w << " " << u << endl;
	
	while(w) {
		//~ cout << w << endl;
		ll actv = paths.query(in[w], in[w]).X;
		ll pdist = subtrees.query(in[w], in[w]).X;
		ll newv = subtrees.query(out[G[w][0].X] + 1, out[w]).X - 2LL * pdist;
		
		//~ cout << actv << " " << newv << endl;
		
		paths.insert(in[w], in[w], newv - actv);
		w = p[first[w]];
	}
}

int main() {
	scanf("%d%d%lld", &n, &q, &w);
	for(int i = 1 ; i < n ; i++) {
		int a, b;
		ll c;
		scanf("%d%d%lld", &a, &b, &c);
		G[a].emplace_back(b, c);
		G[b].emplace_back(a, c);
		ecost[i] = c;
		E[i] = {a, b};
	}
	
	dfs(1);
	for(int i = 1 ; i <= n ; i++) {
		for(int j = 0 ; j < G[i].size() ; j++) {
			if(G[i][j].X == p[i]) {
				G[i].erase(G[i].begin() + j);
				break;
			}
		}
	}
	
	first[1] = 1;
	dfs2(1, 0);
	subtrees.process_init();
	paths.process_init();

	//~ for(int i = 1 ; i <= n ; i++)
		//~ cout << i << " "<< first[i] << endl;

	//~ cout << longest_path() << endl;

	ll last = 0;
	while(q--) {
		ll d, e;
		scanf("%lld%lld", &d, &e);
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		
		change_edge(d + 1, e);
		
		//~ for(int i = 1 ; i <= n ; i++)
			//~ cout << i << " " << in[i] << " " << paths.query(in[i], in[i]).X << " " << paths.query(in[i], in[i]).Y << endl;
		
		printf("%lld\n", last = longest_path());
	}
	
	return 0;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:200:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < G[i].size() ; j++) {
                   ~~^~~~~~~~~~~~~
diameter.cpp:187:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &n, &q, &w);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:191:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:221:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &d, &e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14976 KB Output is correct
2 Correct 9 ms 14976 KB Output is correct
3 Correct 22 ms 15104 KB Output is correct
4 Correct 68 ms 15224 KB Output is correct
5 Correct 288 ms 16248 KB Output is correct
6 Correct 9 ms 14976 KB Output is correct
7 Correct 12 ms 15104 KB Output is correct
8 Correct 10 ms 15104 KB Output is correct
9 Correct 15 ms 15104 KB Output is correct
10 Correct 74 ms 15360 KB Output is correct
11 Correct 322 ms 16376 KB Output is correct
12 Correct 12 ms 15488 KB Output is correct
13 Correct 12 ms 15616 KB Output is correct
14 Correct 18 ms 15616 KB Output is correct
15 Correct 78 ms 15864 KB Output is correct
16 Correct 335 ms 17016 KB Output is correct
17 Correct 55 ms 24808 KB Output is correct
18 Correct 56 ms 24780 KB Output is correct
19 Correct 63 ms 24940 KB Output is correct
20 Correct 131 ms 25192 KB Output is correct
21 Correct 428 ms 26472 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15104 KB Output is correct
2 Correct 80 ms 15300 KB Output is correct
3 Correct 370 ms 15864 KB Output is correct
4 Correct 713 ms 16744 KB Output is correct
5 Correct 24 ms 16128 KB Output is correct
6 Correct 113 ms 16256 KB Output is correct
7 Incorrect 659 ms 16888 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1124 ms 29816 KB Output is correct
2 Correct 1288 ms 29940 KB Output is correct
3 Correct 1150 ms 29816 KB Output is correct
4 Correct 1189 ms 29816 KB Output is correct
5 Correct 1133 ms 30036 KB Output is correct
6 Correct 997 ms 29804 KB Output is correct
7 Correct 681 ms 32944 KB Output is correct
8 Correct 745 ms 32932 KB Output is correct
9 Correct 556 ms 32888 KB Output is correct
10 Correct 682 ms 32888 KB Output is correct
11 Correct 679 ms 32596 KB Output is correct
12 Correct 456 ms 31596 KB Output is correct
13 Correct 364 ms 37496 KB Output is correct
14 Correct 348 ms 37496 KB Output is correct
15 Correct 335 ms 37496 KB Output is correct
16 Correct 361 ms 37496 KB Output is correct
17 Correct 357 ms 36980 KB Output is correct
18 Correct 330 ms 33424 KB Output is correct
19 Correct 333 ms 37496 KB Output is correct
20 Correct 347 ms 37496 KB Output is correct
21 Correct 342 ms 37624 KB Output is correct
22 Correct 351 ms 37496 KB Output is correct
23 Correct 348 ms 36980 KB Output is correct
24 Correct 319 ms 33388 KB Output is correct

Subtask #6
0 / 27.0

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