oj.uz

Submission #491567

# Submission time Handle Problem Language Result Execution time Memory
491567 2021-12-03T10:21:19 Z errorgorn Synchronization (JOI13_synchronization) C++17
100 / 100
 934 ms 131784 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[200005];

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

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

int n,u,q;
vector<ii> al[100005];
vector<ii> v[100005];
vector<ii> v2[100005];

bool used[100005];
int ss[100005];

void dfs_sz(int i,int p){
	ss[i]=1;
	for (auto &it:al[i]){
		if (it.fi==p || used[it.fi]) continue;
		dfs_sz(it.fi,i);
		ss[i]+=ss[it.fi];
	}
}

struct dat{
	int val;
	dat *c1,*c2;
	
	dat(int val) : val(val){
		c1=c2=nullptr;
	}
	
	dat(dat *c1,dat *c2) : c1(c1), c2(c2){
		val=-1;
	}
};

map<int,int> m[100005]; 
map<int,dat*> m2[100005]; 

void rec(dat *u,vector<int> &v){
	if (u->val!=-1) v.pub(u->val);
	else rec(u->c1,v),rec(u->c2,v);
}

void dfs1(int i,int p){
	m[i].clear();
	
	for (auto &it:al[i]){
		if (it.se==p || used[it.fi]) continue;
		
		dfs1(it.fi,it.se);
		//merge them together
		if (sz(m[it.fi])>sz(m[i])) swap(m[it.fi],m[i]);
		for (auto [key,val]:m[it.fi]){
			m[i][key]+=val;
		}
	}
	
	m[i][-1]=1;
	
	int curr=-1;
	for (auto &it:v[p]){
		while (true){
			auto iter=m[i].lb(curr);
			if (iter==m[i].end()) break;
			if ((*iter).fi>=it.fi) break;
			
			m[i][it.fi]+=(*iter).se;
			
			m[i].erase(iter);
		}
		
		curr=it.se+1;
	}
	
	while (!m[i].empty() && (*--m[i].end()).fi>=curr){
		m[i].erase(--m[i].end());
	}
}

void dfs2(int i,int p){
	m2[i].clear();
	
	for (auto &it:al[i]){
		if (it.se==p || used[it.fi]) continue;
		
		dfs2(it.fi,it.se);
		//merge them together
		if (sz(m2[it.fi])>sz(m2[i])) swap(m2[it.fi],m2[i]);
		for (auto [key,val]:m2[it.fi]){
			if (m2[i].count(key)) m2[i][key]=new dat(m2[i][key],val);
			else m2[i][key]=val;
		}
	}
	
	m2[i][-1]=new dat(i);
	
	int curr=-1;
	for (auto &it:v2[p]){
		while (true){
			auto iter=m2[i].lb(curr);
			if (iter==m2[i].end()) break;
			if ((*iter).fi>=it.fi) break;
			
			if (m2[i].count(it.fi)) m2[i][it.fi]=new dat(m2[i][it.fi],(*iter).se);
			else m2[i][it.fi]=(*iter).se;
			
			m2[i].erase(iter);
		}
		
		curr=it.se+1;
	}
	
	while (!m2[i].empty() && (*--m2[i].end()).fi>=curr){
		m2[i].erase(--m2[i].end());
	}
}

int ans[100005];

void centroid(int i){
	dfs_sz(i,-1);
	
	int curr=i,currp=-1;
	int sz=ss[i];
	
	while (true){
		bool flag=false;
		
		for (auto &it:al[curr]){
			if (it.fi==currp || used[it.fi]) continue;
			if (ss[it.fi]>=sz/2){
				currp=curr;
				curr=it.fi;
				flag=true;
				break;
			}
		}
		
		if (!flag) break;
	}
	
	used[curr]=true;
	
	vector<int> temp;
	for (auto &it:al[curr]) if (!used[it.fi]){
		dfs1(it.fi,it.se);
		dfs2(it.fi,it.se);
		
		for (auto [key,val]:m[it.fi]){
			upd(key,val);
		}
	}
	upd(0,1);
	
	ans[curr]+=query(200003);
	
	for (auto &it:al[curr]) if (!used[it.fi]){
		for (auto [key,val]:m[it.fi]){
			upd(key,-val);
		}
		
		for (auto [key,val]:m2[it.fi]){
			temp.clear();
			rec(val,temp);
			for (auto &it:temp){
				ans[it]+=query(u-key);
			}
		}
		
		for (auto [key,val]:m[it.fi]){
			upd(key,val);
		}
	}
	
	for (auto &it:al[curr]) if (!used[it.fi]){
		for (auto [key,val]:m[it.fi]){
			upd(key,-val);
		}
	}
	upd(0,-1);
	
	for (auto &it:al[curr]) if (!used[it.fi]) centroid(it.fi);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>u>>q;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(ii(b,x));
		al[b].pub(ii(a,x));
	}
	
	rep(x,0,u){
		cin>>a;
		
		if (v[a].empty() || v[a].back().se!=-1) v[a].pub(ii(x,-1));
		else v[a].back().se=x;
	}
	
	rep(x,1,n+1) if (!v[x].empty() && v[x].back().se==-1) v[x].back().se=u;
	rep(x,1,n+1){
		v2[x]=v[x];
		reverse(all(v2[x]));
		for (auto &it:v2[x]){
			it=ii(u-it.se,u-it.fi);
		}
	}
	
	// rep(x,1,n){
		// cout<<x<<": "; for (auto &it:v[x]) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
	// }
	// rep(x,1,n){
		// cout<<x<<": "; for (auto &it:v2[x]) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
	// }
	
	centroid(1);
	
	//rep(x,1,n+1) cout<<ans[x]<<" "; cout<<endl;
	
	while (q--){
		cin>>a;
		cout<<ans[a]<<endl;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 9 ms 16716 KB Output is correct
4 Correct 9 ms 16700 KB Output is correct
5 Correct 9 ms 16716 KB Output is correct
6 Correct 13 ms 17188 KB Output is correct
7 Correct 57 ms 21972 KB Output is correct
8 Correct 57 ms 21960 KB Output is correct
9 Correct 61 ms 22172 KB Output is correct
10 Correct 890 ms 77484 KB Output is correct
11 Correct 868 ms 78556 KB Output is correct
12 Correct 683 ms 112376 KB Output is correct
13 Correct 137 ms 44296 KB Output is correct
14 Correct 911 ms 88980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 94104 KB Output is correct
2 Correct 459 ms 93136 KB Output is correct
3 Correct 760 ms 130812 KB Output is correct
4 Correct 779 ms 130744 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 10 ms 16732 KB Output is correct
3 Correct 10 ms 16768 KB Output is correct
4 Correct 11 ms 16844 KB Output is correct
5 Correct 10 ms 16736 KB Output is correct
6 Correct 13 ms 17356 KB Output is correct
7 Correct 62 ms 24716 KB Output is correct
8 Correct 701 ms 113188 KB Output is correct
9 Correct 721 ms 113156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 113196 KB Output is correct
2 Correct 740 ms 131028 KB Output is correct
3 Correct 738 ms 131704 KB Output is correct
4 Correct 779 ms 131684 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16716 KB Output is correct
2 Correct 10 ms 16748 KB Output is correct
3 Correct 9 ms 16768 KB Output is correct
4 Correct 10 ms 16764 KB Output is correct
5 Correct 13 ms 17228 KB Output is correct
6 Correct 61 ms 22076 KB Output is correct
7 Correct 934 ms 80344 KB Output is correct
8 Correct 738 ms 113220 KB Output is correct
9 Correct 152 ms 45452 KB Output is correct
10 Correct 926 ms 89872 KB Output is correct
11 Correct 476 ms 95420 KB Output is correct
12 Correct 459 ms 95336 KB Output is correct
13 Correct 757 ms 131784 KB Output is correct