Submission #835338

#	Time	Username	Problem	Language	Result	Execution time	Memory
835338		NotLinux	Synchronization (JOI13_synchronization)	C++17	100 / 100	933 ms	28280 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
const int LN = 1e5 + 7;
int N,M,Q,a[LN],p[LN],lift[LN][20];
vector < int > TREE[LN] , trav = {0};
pair < int , int > ind[LN];
struct SEGT{
	vector < int > tree;
	int tsz;
	void init(int x){
		tsz = x;
		tree.assign(4*x,0);
	}
	void _update(int ind , int l , int r , int ul , int ur , int uv){
		if(l >= ul and r <= ur)tree[ind] += uv;
		else if(l > ur or r < ul)return;
		else {
			int mid = (l+r)/2;
			_update(ind*2,l,mid,ul,ur,uv);
			_update(ind*2+1,mid+1,r,ul,ur,uv);
		}
	}
	void update(int ul , int ur , int uv){
		_update(1,1,tsz,ul,ur,uv);
	}
	int _query(int ind , int l , int r , int qp){
		if(l == r){
			return tree[ind];
		}
		int mid = (l+r)/2;
		if(mid >= qp)return _query(ind*2,l,mid,qp) + tree[ind];
		else return _query(ind*2+1,mid+1,r,qp) + tree[ind];
	}
	int query(int qp){
		return _query(1,1,tsz,qp);
	}
} segt;
void dfs1(int node , int past){
	ind[node].first = sz(trav);
	trav.push_back(node);
	lift[node][0] = past;
	for(auto itr : TREE[node]){
		if(itr == past)continue;
		dfs1(itr,node);
	}
	ind[node].second = sz(trav)-1;
}
inline void subtree_update(int node , int uv){
	segt.update(ind[node].first , ind[node].second , uv);
}
inline int find_root(int node){
	for(int i = 19;i>=0;i--){
		int newnode = lift[node][i];
		if(segt.query(ind[node].first) == segt.query(ind[newnode].first))node = newnode;
	}
	return node;
}
inline void merge(int u , int v){// u E par[v]
	u = find_root(u);
	v = find_root(v);
	if(ind[u].first > ind[v].first)swap(u,v);
	a[u] = a[u] + a[v] - p[v];
	a[v] = p[v] = 0;
	segt.update(ind[v].first,ind[v].second,-1);
}
inline void unmerge(int u, int v){// u E par[v]
	if(ind[u].first > ind[v].first)swap(u,v);
	u = find_root(u);
	a[v] = p[v] = a[u];
	segt.update(ind[v].first,ind[v].second,1);
}
void dfs2(int node , int past){
	if(a[node] == 0)a[node] = a[past];
	for(auto itr : TREE[node]){
		if(itr == past)continue;
		dfs2(itr,node);
	}
}
void solve(){
	cin >> N >> M >> Q;
	vector < array < int , 3 > > edges;
	for(int i = 1;i<N;i++){
		int XI,YI;cin >> XI >> YI;
		TREE[XI].push_back(YI);
		TREE[YI].push_back(XI);
		edges.push_back({XI,YI,0});
	}
	dfs1(1,1);
	segt.init(sz(trav));
	for(int i = 1;i<=N;i++){
		a[i] = 1;
		segt.update(ind[i].first,ind[i].second,1);
	}
	lift[1][0] = 1;
	for(int i = 1;i<20;i++){
		for(int j = 1;j<=N;j++){
			lift[j][i] = lift[lift[j][i-1]][i-1];
		}
	}
	while(M--){
		int DJ;cin >> DJ;DJ--;
		if(edges[DJ][2])unmerge(edges[DJ][0] , edges[DJ][1]);
		else merge(edges[DJ][0] , edges[DJ][1]);
		edges[DJ][2] = 1 - edges[DJ][2];
	}
	dfs2(1,1);
	while(Q--){
		int CK;cin >> CK;
		cout << a[CK] << endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}
/*
 - dont loop over same ideas
 - abandon the problem if you have no idea
 - think about implementation
*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40