oj.uz

Submission #132157

# Submission time Handle Problem Language Result Execution time Memory
132157 2019-07-18T11:12:01 Z imyujin Construction of Highway (JOI18_construction) C++14
0 / 100
 2000 ms 134552 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005
#define fi first
#define se second
#define rb(x) ((x) & (-(x)))

typedef long long lint;
typedef pair<int, int> pii;

int C[MAXN], A[MAXN], B[MAXN];
vector<int> ed[MAXN];
int par[20][MAXN], dep[MAXN], dfsord[MAXN], dfsr[MAXN], dfsn;
int addord[MAXN];
int cs[MAXN], ch[MAXN];
int seg[4 * MAXN];
int bit[MAXN];
int xxxx = 0;

int anc(int x, int d) {
	for(int i = 0; i < 20; i++) if((dep[x] - d) & (1 << i)) x = par[i][x];
	return x;
}

void dfs(int x) {
	dfsord[x] = dfsr[x] = ++dfsn;
	for(auto a : ed[x]) {
		par[0][a] = x;
		dep[a] = dep[x] + 1;
		dfs(a);
		dfsr[x] = dfsr[a];
	}
}

void updseg(int idx, int l, int r, int x, int y) {
	if(l == r) seg[idx] = y;
	else {
		int m = (l + r) / 2;
		if(x <= m) updseg(idx * 2, l, m, x, y);
		else updseg(idx * 2 + 1, m + 1, r, x, y);
		seg[idx] = max(seg[idx * 2], seg[idx * 2 + 1]);
	}
}

int gseg(int idx, int l, int r, int x, int y) {
	//if(idx == 1 && ++xxxx < 100) printf("gseg(x = %d, y = %d)\n", x, y);
	if(x <= l && r <= y) return seg[idx];
	if(r < x || y < l) return -1;
	int m = (l + r) / 2;
	return max(gseg(idx * 2, l, m, x, y), gseg(idx * 2 + 1, m + 1, r, x, y));
}

void updbit(int x, int y) { for(;x < MAXN; x += rb(x)) bit[x] += y; }
int gbit(int x) { int ans = 0; for(; x > 0; x -= rb(x)) ans += bit[x]; return ans; }

int main() {
	int N;

	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", C + i);
	for(int i = 1; i < N; i++) scanf("%d%d", A + i, B + i);

	for(int i = 1; i < N; i++) ed[A[i]].push_back(B[i]);
	dep[1] = 1;
	dfs(1);
	for(int i = 1; i < 20; i++) for(int j = 1; j <= N; j++) par[i][j] = par[i - 1][par[i - 1][j]];

	for(int i = 1; i <= N; i++) cs[i - 1] = C[i];
	sort(cs, cs + N);
	for(int i = 1; i <= N; i++) C[i] = lower_bound(cs, cs + N, C[i]) - cs + 1;
	for(int i = 1; i < 4 * N; i++) seg[i] = -1;
	updseg(1, 1, N, dfsord[1], 0);
	ch[C[1]] = 1;
	B[0] = 1;
	//printf("*\n");

	for(int i = 1; i < N; i++) {
		vector<pii> v;
		for(int t = A[i]; t != 0;) {
			//if(++xxxx < 100) printf("i = %d, t = %d\n", i, t);
			int c = C[B[gseg(1, 1, N, dfsord[t], dfsr[t])]];
			//if(++xxxx < 100) printf("c = %d\n", c);
			v.push_back(make_pair(c, dep[t] - ch[c] + 1));
			int k = anc(t, ch[c] - 1);
			ch[c] = dep[t] + 1;
			t = k;
		}
		lint ans = 0ll;
		//for(auto a : v) printf("a = (%d, %d)\n", a.fi, a.se);
		for(auto a : v) {
			ans += a.se * gbit(a.fi - 1);
			updbit(a.fi, a.se);
		}
		for(auto a : v) updbit(a.fi, -a.se);
		ch[C[B[i]]] = 1;
		updseg(1, 1, N, dfsord[B[i]], i);
		printf("%lld\n", ans);
	}

	return 0;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
construction.cpp:61:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d", C + i);
                              ~~~~~^~~~~~~~~~~~~
construction.cpp:62:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i < N; i++) scanf("%d%d", A + i, B + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2940 KB Output is correct
6 Correct 5 ms 2896 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2936 KB Output is correct
9 Correct 5 ms 2936 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Correct 5 ms 2936 KB Output is correct
15 Correct 5 ms 2936 KB Output is correct
16 Correct 5 ms 2936 KB Output is correct
17 Correct 5 ms 2936 KB Output is correct
18 Correct 5 ms 2936 KB Output is correct
19 Correct 5 ms 2936 KB Output is correct
20 Correct 5 ms 2936 KB Output is correct
21 Correct 5 ms 2936 KB Output is correct
22 Execution timed out 2058 ms 134552 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2940 KB Output is correct
6 Correct 5 ms 2896 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2936 KB Output is correct
9 Correct 5 ms 2936 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Correct 5 ms 2936 KB Output is correct
15 Correct 5 ms 2936 KB Output is correct
16 Correct 5 ms 2936 KB Output is correct
17 Correct 5 ms 2936 KB Output is correct
18 Correct 5 ms 2936 KB Output is correct
19 Correct 5 ms 2936 KB Output is correct
20 Correct 5 ms 2936 KB Output is correct
21 Correct 5 ms 2936 KB Output is correct
22 Execution timed out 2058 ms 134552 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2940 KB Output is correct
6 Correct 5 ms 2896 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2936 KB Output is correct
9 Correct 5 ms 2936 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Correct 5 ms 2936 KB Output is correct
15 Correct 5 ms 2936 KB Output is correct
16 Correct 5 ms 2936 KB Output is correct
17 Correct 5 ms 2936 KB Output is correct
18 Correct 5 ms 2936 KB Output is correct
19 Correct 5 ms 2936 KB Output is correct
20 Correct 5 ms 2936 KB Output is correct
21 Correct 5 ms 2936 KB Output is correct
22 Execution timed out 2058 ms 134552 KB Time limit exceeded
23 Halted 0 ms 0 KB -