Submission #873474

#	Time	Username	Problem	Language	Result	Execution time	Memory
873474		KN200711	Synchronization (JOI13_synchronization)	C++14	100 / 100	129 ms	19408 KiB

synchronization

# 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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40