oj.uz

Submission #491716

# Submission time Handle Problem Language Result Execution time Memory
491716 2021-12-04T02:08:34 Z errorgorn Synchronization (JOI13_synchronization) C++17
100 / 100
 281 ms 26156 KB 
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int fen[100005];

void upd(int i,int k){
	while (i<100005){
		fen[i]+=k;
		i+=i&-i;
	}
}

void upd(int i,int j,int k){
	upd(i,k),upd(j+1,-k);
}

int query(int i){
	int res=0;
	while (i){
		res+=fen[i];
		i-=i&-i;
	}
	return res;
}

int n,m,q;
vector<ii> al[100005];
int tkd[100005][18];
int pos[100005];
int in[100005];
int out[100005];

int TIME=0;

void dfs(int i,int p){
	in[i]=++TIME;
	for (auto &it:al[i]){
		if (it.fi==p) continue;
		
		pos[it.se]=it.fi;
		int curr=tkd[it.fi][0]=i;
		rep(x,0,17){
			if (curr==-1) break;
			curr=tkd[it.fi][x+1]=tkd[curr][x];
		}
		
		dfs(it.fi,i);
	}
	out[i]=TIME;
}

int head(int i){
	int curr=i;
	rep(x,18,0) if (tkd[curr][x]!=-1 && query(in[tkd[curr][x]])==query(in[i])){
		curr=tkd[curr][x];
	}
	return curr;
}

bool tog[100005];
int num[100005];
int com[100005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m>>q;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(ii(b,x));
		al[b].pub(ii(a,x));
	}
	
	memset(tkd,-1,sizeof(tkd));
	dfs(1,-1);
	
	rep(x,1,n+1){
		upd(in[x],out[x],1);
		num[x]=1;
	}
	
	rep(x,0,m){
		cin>>a;
		a=pos[a];
		
		if (!tog[a]){
			int h=head(tkd[a][0]);
			num[h]=num[h]+num[a]-com[a];
			upd(in[a],out[a],-1);
		}
		else{
			int h=head(a);
			num[a]=com[a]=num[h];
			upd(in[a],out[a],1);
		}
		tog[a]^=true;
	}
	
	rep(x,0,q){
		cin>>a;
		cout<<num[head(a)]<<endl;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 4 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 14 ms 10700 KB Output is correct
8 Correct 14 ms 10700 KB Output is correct
9 Correct 14 ms 10712 KB Output is correct
10 Correct 187 ms 19636 KB Output is correct
11 Correct 209 ms 19468 KB Output is correct
12 Correct 195 ms 25396 KB Output is correct
13 Correct 74 ms 18760 KB Output is correct
14 Correct 126 ms 18532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 21620 KB Output is correct
2 Correct 75 ms 21540 KB Output is correct
3 Correct 116 ms 24476 KB Output is correct
4 Correct 113 ms 24460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 4 ms 9756 KB Output is correct
3 Correct 4 ms 9676 KB Output is correct
4 Correct 4 ms 9676 KB Output is correct
5 Correct 4 ms 9676 KB Output is correct
6 Correct 6 ms 9880 KB Output is correct
7 Correct 20 ms 11328 KB Output is correct
8 Correct 281 ms 26156 KB Output is correct
9 Correct 259 ms 26156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 26100 KB Output is correct
2 Correct 147 ms 25484 KB Output is correct
3 Correct 146 ms 25660 KB Output is correct
4 Correct 152 ms 25640 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 4 ms 9716 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 18 ms 10760 KB Output is correct
7 Correct 195 ms 20348 KB Output is correct
8 Correct 273 ms 26152 KB Output is correct
9 Correct 92 ms 19868 KB Output is correct
10 Correct 144 ms 19856 KB Output is correct
11 Correct 105 ms 22900 KB Output is correct
12 Correct 98 ms 22864 KB Output is correct
13 Correct 143 ms 25616 KB Output is correct