oj.uz

답안 #207928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207928 2020-03-09T13:00:03 Z E869120 Dynamic Diameter (CEOI19_diameter) C++14
11 / 100
 5000 ms 1048580 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	long long val, lazy;
	int cl, cr, dep;
};

class LazySegmentTree {
public:
	int depth_ = 0;
	int size_ = 1;
	vector<Node> G;

	void init(int sz) {
		while (size_ <= sz) { size_ *= 2; depth_++; }
		G.push_back(Node{ 0LL, 0LL, -1, -1, depth_ * 2 });
	}
	void refresh(int pos) {
		if (G[pos].dep >= 1) {
			if (G[pos].cl == -1) { G[pos].cl = G.size(); G.push_back(Node{ 0LL, 0LL, -1, -1, G[pos].dep - 1 }); }
			if (G[pos].cr == -1) { G[pos].cr = G.size(); G.push_back(Node{ 0LL, 0LL, -1, -1, G[pos].dep - 1 }); }
			G[G[pos].cl].lazy += G[pos].lazy;
			G[G[pos].cr].lazy += G[pos].lazy;
			G[pos].lazy = 0;
			G[pos].val = max(G[G[pos].cl].val + G[G[pos].cl].lazy, G[G[pos].cr].val + G[G[pos].cr].lazy);
		}
		else {
			G[pos].val += G[pos].lazy;
			G[pos].lazy = 0;
		}
	}
	void add_(int lx, int rx, int ly, int ry, long long x, int ax, int bx, int ay, int by, int u) {
		if (bx <= lx || rx <= ax || by <= ly || ry <= ay) return;
		if (lx <= ax && bx <= rx && ly <= ay && by <= ry) { G[u].lazy += x; return; }
		refresh(u);
		if (G[u].dep >= depth_ + 1) {
			add_(lx, rx, ly, ry, x, ax, bx, ay, (ay + by) >> 1, G[u].cl);
			add_(lx, rx, ly, ry, x, ax, bx, (ay + by) >> 1, by, G[u].cr);
		}
		else {
			add_(lx, rx, ly, ry, x, ax, (ax + bx) >> 1, ay, by, G[u].cl);
			add_(lx, rx, ly, ry, x, (ax + bx) >> 1, bx, ay, by, G[u].cr);
		}
		refresh(u);
	}
	void add(int lx, int rx, int ly, int ry, long long x) {
		add_(lx, rx, ly, ry, x, 0, size_, 0, size_, 0);
	}
	long long getans() {
		return G[0].val + G[0].lazy;
	}
};

long long N, A[1 << 18], B[1 << 18], C[1 << 18];
long long Q, D[1 << 18], E[1 << 18];
long long W;
vector<int> X[1 << 18];

int cl[1 << 18], cr[1 << 18], depth[1 << 18], cnts;
LazySegmentTree Z;

void dfs(int pos, int dep) {
	cnts++; cl[pos] = cnts; depth[pos] = dep;
	for (int i : X[pos]) {
		if (cl[i] == 0) dfs(i, dep + 1);
	}
	cr[pos] = cnts;
}

int main() {
	scanf("%lld%lld%lld", &N, &Q, &W);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= Q; i++) scanf("%lld%lld", &D[i], &E[i]);
	dfs(1, 0);
	Z.init(N + 2);

	for (int i = 1; i <= N - 1; i++) {
		if (depth[A[i]] > depth[B[i]]) swap(A[i], B[i]);
		Z.add(cl[B[i]], cr[B[i]] + 1, 1, N + 1, C[i]);
		Z.add(cl[B[i]], cr[B[i]] + 1, cl[B[i]], cr[B[i]] + 1, -C[i]);

		Z.add(1, N + 1, cl[B[i]], cr[B[i]] + 1, C[i]);
		Z.add(cl[B[i]], cr[B[i]] + 1, cl[B[i]], cr[B[i]] + 1, -C[i]);
	}

	long long last = 0;
	for (int i = 1; i <= Q; i++) {
		D[i] = (D[i] + last) % (N - 1) + 1;
		E[i] = (E[i] + last) % W;

		int pos = B[D[i]];
		Z.add(cl[pos], cr[pos] + 1, 1, N + 1, E[i] - C[D[i]]);
		Z.add(cl[pos], cr[pos] + 1, cl[pos], cr[pos] + 1, C[D[i]] - E[i]);

		Z.add(1, N + 1, cl[pos], cr[pos] + 1, E[i] - C[D[i]]);
		Z.add(cl[pos], cr[pos] + 1, cl[pos], cr[pos] + 1, C[D[i]] - E[i]);
		C[D[i]] = E[i];
		long long rem = Z.getans();
		last = rem;
		printf("%lld\n", rem);
	}
	return 0;
}

Compilation message

diameter.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
diameter.cpp: In function 'int main()':
diameter.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &N, &Q, &W);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:81:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) scanf("%lld%lld", &D[i], &E[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6520 KB Output is correct
2 Correct 9 ms 6648 KB Output is correct
3 Correct 17 ms 6520 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6520 KB Output is correct
6 Correct 9 ms 6520 KB Output is correct
7 Correct 11 ms 6904 KB Output is correct
8 Correct 12 ms 6904 KB Output is correct
9 Correct 12 ms 6904 KB Output is correct
10 Correct 11 ms 6904 KB Output is correct
11 Correct 12 ms 6904 KB Output is correct
12 Correct 14 ms 6904 KB Output is correct
13 Correct 20 ms 7920 KB Output is correct
14 Correct 16 ms 7664 KB Output is correct
15 Correct 18 ms 7788 KB Output is correct
16 Correct 17 ms 7920 KB Output is correct
17 Correct 18 ms 7664 KB Output is correct
18 Correct 23 ms 7660 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6520 KB Output is correct
2 Correct 9 ms 6648 KB Output is correct
3 Correct 17 ms 6520 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6520 KB Output is correct
6 Correct 9 ms 6520 KB Output is correct
7 Correct 11 ms 6904 KB Output is correct
8 Correct 12 ms 6904 KB Output is correct
9 Correct 12 ms 6904 KB Output is correct
10 Correct 11 ms 6904 KB Output is correct
11 Correct 12 ms 6904 KB Output is correct
12 Correct 14 ms 6904 KB Output is correct
13 Correct 20 ms 7920 KB Output is correct
14 Correct 16 ms 7664 KB Output is correct
15 Correct 18 ms 7788 KB Output is correct
16 Correct 17 ms 7920 KB Output is correct
17 Correct 18 ms 7664 KB Output is correct
18 Correct 23 ms 7660 KB Output is correct
19 Correct 2710 ms 72472 KB Output is correct
20 Correct 2934 ms 72472 KB Output is correct
21 Correct 4439 ms 72472 KB Output is correct
22 Execution timed out 5072 ms 72600 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6648 KB Output is correct
2 Correct 10 ms 6648 KB Output is correct
3 Correct 19 ms 6648 KB Output is correct
4 Correct 101 ms 7164 KB Output is correct
5 Correct 504 ms 9400 KB Output is correct
6 Correct 10 ms 6520 KB Output is correct
7 Correct 117 ms 23120 KB Output is correct
8 Correct 137 ms 23120 KB Output is correct
9 Correct 409 ms 23120 KB Output is correct
10 Correct 3139 ms 23652 KB Output is correct
11 Execution timed out 5068 ms 25684 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1152 ms 72472 KB Output is correct
2 Execution timed out 5090 ms 72728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1492 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6520 KB Output is correct
2 Correct 9 ms 6648 KB Output is correct
3 Correct 17 ms 6520 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6520 KB Output is correct
6 Correct 9 ms 6520 KB Output is correct
7 Correct 11 ms 6904 KB Output is correct
8 Correct 12 ms 6904 KB Output is correct
9 Correct 12 ms 6904 KB Output is correct
10 Correct 11 ms 6904 KB Output is correct
11 Correct 12 ms 6904 KB Output is correct
12 Correct 14 ms 6904 KB Output is correct
13 Correct 20 ms 7920 KB Output is correct
14 Correct 16 ms 7664 KB Output is correct
15 Correct 18 ms 7788 KB Output is correct
16 Correct 17 ms 7920 KB Output is correct
17 Correct 18 ms 7664 KB Output is correct
18 Correct 23 ms 7660 KB Output is correct
19 Correct 2710 ms 72472 KB Output is correct
20 Correct 2934 ms 72472 KB Output is correct
21 Correct 4439 ms 72472 KB Output is correct
22 Execution timed out 5072 ms 72600 KB Time limit exceeded
23 Halted 0 ms 0 KB -