oj.uz

Submission #49903

# Submission time Handle Problem Language Result Execution time Memory
49903 2018-06-04T14:32:23 Z tmwilliamlin168 Synchronization (JOI13_synchronization) C++14
100 / 100
 321 ms 20804 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 6 ms 2788 KB Output is correct
3 Correct 4 ms 2964 KB Output is correct
4 Correct 2 ms 2964 KB Output is correct
5 Correct 4 ms 2964 KB Output is correct
6 Correct 7 ms 2992 KB Output is correct
7 Correct 15 ms 4272 KB Output is correct
8 Correct 14 ms 4272 KB Output is correct
9 Correct 14 ms 4272 KB Output is correct
10 Correct 261 ms 15460 KB Output is correct
11 Correct 321 ms 15592 KB Output is correct
12 Correct 252 ms 20272 KB Output is correct
13 Correct 81 ms 20272 KB Output is correct
14 Correct 107 ms 20272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 20272 KB Output is correct
2 Correct 67 ms 20272 KB Output is correct
3 Correct 107 ms 20272 KB Output is correct
4 Correct 88 ms 20272 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20272 KB Output is correct
2 Correct 4 ms 20272 KB Output is correct
3 Correct 3 ms 20272 KB Output is correct
4 Correct 4 ms 20272 KB Output is correct
5 Correct 4 ms 20272 KB Output is correct
6 Correct 6 ms 20272 KB Output is correct
7 Correct 28 ms 20272 KB Output is correct
8 Correct 299 ms 20420 KB Output is correct
9 Correct 298 ms 20420 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 20468 KB Output is correct
2 Correct 183 ms 20740 KB Output is correct
3 Correct 141 ms 20804 KB Output is correct
4 Correct 127 ms 20804 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20804 KB Output is correct
2 Correct 4 ms 20804 KB Output is correct
3 Correct 4 ms 20804 KB Output is correct
4 Correct 4 ms 20804 KB Output is correct
5 Correct 5 ms 20804 KB Output is correct
6 Correct 20 ms 20804 KB Output is correct
7 Correct 226 ms 20804 KB Output is correct
8 Correct 296 ms 20804 KB Output is correct
9 Correct 71 ms 20804 KB Output is correct
10 Correct 117 ms 20804 KB Output is correct
11 Correct 88 ms 20804 KB Output is correct
12 Correct 87 ms 20804 KB Output is correct
13 Correct 132 ms 20804 KB Output is correct