Submission #49903

#	Time	Username	Problem	Language	Result	Execution time	Memory
49903		tmwilliamlin168	Synchronization (JOI13_synchronization)	C++14	100 / 100	321 ms	20804 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(int x) {
	int rev=x, count = 0;
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
	putchar_unlocked('\n');
}

const int mxN=1e5;
int n, m, q, x[mxN-1], y[mxN-1], st[mxN], en[mxN], dt, ft[mxN+1], v[mxN], lc[mxN-1], anc[mxN][17], dj;
vector<int> adj[mxN];

inline void upd(int i, int x) {
	for(++i; i<=n; i+=i&-i)
		ft[i]+=x;
}

inline int qry(int i) {
	int r=0;
	for(++i; i; i-=i&-i)
		r+=ft[i];
	return r;
}

void dfs(int u, int p) {
	st[u]=dt++;
	anc[u][0]=p;
	for(int i=1; i<17; ++i)
		anc[u][i]=anc[u][i-1]==-1?-1:anc[anc[u][i-1]][i-1];
	for(int v : adj[u])
		if(v!=p)
			dfs(v, u);
	en[u]=dt;
}

inline int find(int x) {
	int a=qry(st[x]), b=x;
	for(int i=16; i>=0; --i)
		if(anc[b][i]!=-1&&qry(st[anc[b][i]])==a)
			b=anc[b][i];
	return b;
}

int main() {
	n=in(), m=in(), q=in();
	for(int i=0; i<n-1; ++i) {
		x[i]=in()-1, y[i]=in()-1;
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	dfs(0, -1);
	for(int i=0; i<n; ++i) {
		v[i]=1;
		upd(st[i], 1);
		upd(en[i], -1);
	}
	for(int i=0; i<n-1; ++i)
		if(anc[x[i]][0]==y[i])
			swap(x[i], y[i]);
	while(m--) {
		dj=in()-1;
		int x2=find(x[dj]);
		if(lc[dj]==-1) {
			upd(st[y[dj]], 1);
			upd(en[y[dj]], -1);
			lc[dj]=v[y[dj]]=v[x2];
		} else {
			upd(st[y[dj]], -1);
			upd(en[y[dj]], 1);
			v[x2]+=v[y[dj]]-lc[dj];
			lc[dj]=-1;
		}
	}
	while(q--)
		out(v[find(in()-1)]);
}

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