제출 #491567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491567		errorgorn	동기화 (JOI13_synchronization)	C++17	100 / 100	934 ms	131784 KiB

synchronization

// 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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40