oj.uz

Submission #873474

# Submission time Handle Problem Language Result Execution time Memory
873474 2023-11-15T07:00:47 Z KN200711 Synchronization (JOI13_synchronization) C++14
100 / 100
 129 ms 19408 KB 
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

int N, M, Q;
int ans[100001], lst[100001];
int dpt[100001], sz[100001], mx[100001], bg[100001], pos[100001], par[100001], in[100001], rt[100001], t;
vector< pair<int, int> > sp;
vector<int> edge[100001];
bool tr[100001];

void dfs(int a, int pr, int dt) {
	par[a] = pr;
	dpt[a] = dt;
	sz[a] = 1;
	mx[a] = -1;
	bg[a] = -1;
	for(int i=0;i<edge[a].size();i++) {
		if(edge[a][i] == pr) continue;
		dfs(edge[a][i], a, dt+1);
		sz[a] += sz[edge[a][i]];
		if(mx[a] < sz[edge[a][i]]) {
			mx[a] = sz[edge[a][i]];
			bg[a] = edge[a][i];
		}
	}
}

void build_hld(int a, int pr, int root) {
	rt[a] = root;
	pos[t] = a;
	in[a] = t++;
	// rt[a] = root; // duplicate
	if(bg[a] != -1) build_hld(bg[a], a, root);
	for(int i=0;i<edge[a].size();i++) {
		if(edge[a][i] == pr || edge[a][i] == bg[a]) continue;
		build_hld(edge[a][i], a, edge[a][i]); // root = ch
	}
}

int fen[100001];

void add(int a, int x) {
	while(a <= 1e5) {
		fen[a] += x;
		a += a&(-a);
	}
}

int qry(int a) {
	int as = 0;
	while(a > 0) {
		as += fen[a];
		a -= a&(-a);
	}
	return as;
}

int binser(int a) {
	int id = 0, sum = 0;
	for(int i=20;i>=0;i--) {
		id += (1 << i);
		if(id <= 1e5 && sum + fen[id] <= a) {
			sum += fen[id];
		} else {
			id -= (1 << i);
		}
	}
	return id;
}

int find(int a) {
	while(true) {
		int L = qry(1e5 - in[a] - 1);
		L = binser(L);
	//	cout<<"L : "<<L<<endl;
	//	if(a != 0) cout<<a<<" "<<L<<" "<<rt[a]<<endl;
		if(L >= 1e5 - in[rt[a]]) a = par[rt[a]];
		else {
			L++;
			return pos[(int) 1e5 - L];
		}
	}
}

int main() {
	scanf("%d %d %d", &N, &M, &Q);
	for(int i=1;i<N;i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		edge[a].push_back(b);
		edge[b].push_back(a);
		sp.push_back(make_pair(a, b));
	}
	
	dfs(1, 0, 0);
	build_hld(1, 0, 1);
	for(int i=1;i<=N;i++) {
		add(1e5 - in[i], 1);
        ans[i] = 1;
	}
	
	for(int i=0;i<M;i++) {
		int L;
		scanf("%d", &L);
		L--;
		if(dpt[sp[L].fi] < dpt[sp[L].se]) swap(sp[L].fi, sp[L].se);
		
		if(!tr[L]) {
			// sambungin L
			tr[L] = 1;
			int KL = find(sp[L].se);
			ans[KL] += ans[sp[L].fi] - lst[sp[L].fi];
            add(1e5 - in[sp[L].fi], -1);
		} else {
			tr[L] = 0;
            ans[sp[L].fi] = lst[sp[L].fi] = ans[find(sp[L].se)];
			add(1e5 - in[sp[L].fi], 1);
		}
	}
	while(Q--) {
		int v;
		scanf("%d", &v);
        printf("%d\n", ans[find(v)]);
	}
}

Compilation message

synchronization.cpp: In function 'void dfs(int, int, int)':
synchronization.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void build_hld(int, int, int)':
synchronization.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%d", &L);
      |   ~~~~~^~~~~~~~~~
synchronization.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 8 ms 6884 KB Output is correct
8 Correct 8 ms 7004 KB Output is correct
9 Correct 8 ms 7004 KB Output is correct
10 Correct 100 ms 11216 KB Output is correct
11 Correct 113 ms 11204 KB Output is correct
12 Correct 92 ms 18888 KB Output is correct
13 Correct 58 ms 11488 KB Output is correct
14 Correct 92 ms 10948 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 15184 KB Output is correct
2 Correct 57 ms 15048 KB Output is correct
3 Correct 54 ms 18896 KB Output is correct
4 Correct 53 ms 18636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 10 ms 7772 KB Output is correct
8 Correct 101 ms 19076 KB Output is correct
9 Correct 124 ms 18916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 19140 KB Output is correct
2 Correct 82 ms 19340 KB Output is correct
3 Correct 73 ms 19408 KB Output is correct
4 Correct 73 ms 19396 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 11 ms 7004 KB Output is correct
7 Correct 129 ms 11284 KB Output is correct
8 Correct 102 ms 18916 KB Output is correct
9 Correct 90 ms 11784 KB Output is correct
10 Correct 115 ms 11716 KB Output is correct
11 Correct 79 ms 15552 KB Output is correct
12 Correct 80 ms 15636 KB Output is correct
13 Correct 75 ms 19400 KB Output is correct