Submission #871344

#	Time	Username	Problem	Language	Result	Execution time	Memory
871344		KN200711	Synchronization (JOI13_synchronization)	C++14	0 / 100	163 ms	262144 KiB

synchronization

# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

bitset<100000> info[100001];
int N, M, Q, 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;
	if(bg[a] != -1) build_hld(bg[a], a, root);
	for(int i=0;i<edge[a].size();i++) {
		if(edge[a][i] == pr) continue;
		build_hld(edge[a][i], a, a);
	}
}

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);
		info[i][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;
		//	cout<<"sp : "<<sp[L].se<<" "<<find(sp[L].se)<<endl;
			int KL = find(sp[L].se);
			info[KL] |= info[sp[L].fi];
			add(1e5 - in[sp[L].fi], -1);
		} else {
			// dipisah
			tr[L] = 0;
		//	cout<<"sp : "<<sp[L].se<<" "<<find(sp[L].se)<<" "<<sp[L].fi<<" "<<info[find(sp[L].se)].count()<<endl;
			info[sp[L].fi] = info[find(sp[L].se)];
			add(1e5 - in[sp[L].fi], 1);
		}
	//	for(int i=1;i<=N;i++) cout<<info[find(i)].count()<<" ";
	//	cout<<endl;
	}
	while(Q--) {
		int v;
		scanf("%d", &v);
		printf("%d\n", info[find(v)].count());
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'void dfs(int, int, int)':
synchronization.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void build_hld(int, int, int)':
synchronization.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:129:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::size_t' {aka 'long unsigned int'} [-Wformat=]
  129 |   printf("%d\n", info[find(v)].count());
      |           ~^     ~~~~~~~~~~~~~~~~~~~~~
      |            |                        |
      |            int                      std::size_t {aka long unsigned int}
      |           %ld
synchronization.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d", &L);
      |   ~~~~~^~~~~~~~~~
synchronization.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40