oj.uz

Submission #960886

# Submission time Handle Problem Language Result Execution time Memory
960886 2024-04-11T07:32:43 Z pcc Synchronization (JOI13_synchronization) C++17
30 / 100
 211 ms 68636 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;
		dfs(rt);
		done.reset();
		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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 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 10844 KB Output is correct
7 Correct 13 ms 11608 KB Output is correct
8 Correct 15 ms 11608 KB Output is correct
9 Correct 13 ms 11612 KB Output is correct
10 Correct 159 ms 26400 KB Output is correct
11 Correct 165 ms 26424 KB Output is correct
12 Correct 186 ms 30780 KB Output is correct
13 Correct 136 ms 26572 KB Output is correct
14 Correct 163 ms 27160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 30488 KB Output is correct
2 Correct 97 ms 28496 KB Output is correct
3 Correct 102 ms 33404 KB Output is correct
4 Correct 105 ms 32376 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 211 ms 68636 KB Execution killed with signal 11
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 2 ms 10844 KB Output is correct
3 Incorrect 2 ms 10844 KB Output isn't correct
4 Halted 0 ms 0 KB -