oj.uz

Submission #960887

# Submission time Handle Problem Language Result Execution time Memory
960887 2024-04-11T07:33:27 Z pcc Synchronization (JOI13_synchronization) C++17
30 / 100
 8000 ms 33984 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
int bit[mxn];
pii eul[mxn],edges[mxn];
int N,M,Q;
int dep[mxn];
vector<int> tree[mxn];
bitset<mxn> done;
int mv[mxn*2];
int rt;
int par[mxn][20];
int pt = 0;
set<int> st[mxn];

void modify(int p,int v){
	for(;p<mxn;p+=p&-p)bit[p] += v;
	return;
}
int getval(int p){
	int re = 0;
	for(;p>0;p-= p&-p)re += bit[p];
	return re;
}

void dfs(int now){
	eul[now].fs = ++pt;
	for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
	for(auto nxt:tree[now]){
		if(nxt == par[now][0])continue;
		par[nxt][0] = now;
		dep[nxt] = dep[now]+1;
		dfs(nxt);
	}
	eul[now].sc = pt;
	return;
}

void change(int p){
	auto [a,b] = edges[p];
	if(dep[a]>dep[b])swap(a,b);
	if(done[p]){
		done[p] = false;
		modify(eul[b].fs,-1);
		modify(eul[b].sc+1,1);
		return;
	}
	done[p] = true;
	modify(eul[b].fs,1);
	modify(eul[b].sc+1,-1);
	int up = b;
	for(int i = 19;i>=0;i--){
		if(getval(eul[b].fs)-getval(eul[par[up][i]].fs) == dep[b]-dep[par[up][i]])up = par[up][i];
	}
	if(up == b)return;
	if(st[up].size()<st[b].size())st[up].swap(st[b]);
	for(auto &i:st[b])st[up].insert(i);
	st[b].clear();
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>Q;
	for(int i = 1;i<N;i++){
		auto &[a,b] = edges[i];
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 1;i<=M;i++)cin>>mv[i];
	while(Q--){
		cin>>rt;
		par[rt][0] = rt;
		dep[rt] = 0;
		dfs(rt);
		done.reset();
		pt = 0;
		for(int i = 1;i<=N+1;i++)bit[i] = 0;
		for(int i = 1;i<=N;i++)st[i].clear();
		for(int i = 1;i<=N;i++)st[i].insert(i);
		for(int i = 1;i<=M;i++)change(mv[i]);
		cout<<st[rt].size()<<'\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 11096 KB Output is correct
7 Correct 13 ms 11608 KB Output is correct
8 Correct 14 ms 11612 KB Output is correct
9 Correct 12 ms 11672 KB Output is correct
10 Correct 167 ms 26392 KB Output is correct
11 Correct 166 ms 26396 KB Output is correct
12 Correct 152 ms 30784 KB Output is correct
13 Correct 127 ms 26472 KB Output is correct
14 Correct 169 ms 27160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 30584 KB Output is correct
2 Correct 87 ms 28492 KB Output is correct
3 Correct 103 ms 33348 KB Output is correct
4 Correct 90 ms 32180 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10848 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 9 ms 10940 KB Output is correct
4 Correct 6 ms 10840 KB Output is correct
5 Correct 7 ms 10940 KB Output is correct
6 Correct 529 ms 11072 KB Output is correct
7 Execution timed out 8092 ms 12812 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8025 ms 33984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 9 ms 10856 KB Output is correct
5 Correct 588 ms 11004 KB Output is correct
6 Execution timed out 8031 ms 12068 KB Time limit exceeded
7 Halted 0 ms 0 KB -