oj.uz

Submission #835338

# Submission time Handle Problem Language Result Execution time Memory
835338 2023-08-23T13:25:19 Z NotLinux Synchronization (JOI13_synchronization) C++17
100 / 100
 933 ms 28280 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 45 ms 4564 KB Output is correct
8 Correct 43 ms 4564 KB Output is correct
9 Correct 45 ms 4564 KB Output is correct
10 Correct 563 ms 21248 KB Output is correct
11 Correct 617 ms 21236 KB Output is correct
12 Correct 818 ms 27388 KB Output is correct
13 Correct 389 ms 21144 KB Output is correct
14 Correct 384 ms 20600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 24192 KB Output is correct
2 Correct 412 ms 23912 KB Output is correct
3 Correct 378 ms 26824 KB Output is correct
4 Correct 382 ms 26864 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 7 ms 2900 KB Output is correct
7 Correct 71 ms 5324 KB Output is correct
8 Correct 913 ms 28148 KB Output is correct
9 Correct 915 ms 28280 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 28204 KB Output is correct
2 Correct 481 ms 27880 KB Output is correct
3 Correct 485 ms 28008 KB Output is correct
4 Correct 487 ms 28052 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 5 ms 2772 KB Output is correct
6 Correct 57 ms 4612 KB Output is correct
7 Correct 683 ms 22148 KB Output is correct
8 Correct 933 ms 28200 KB Output is correct
9 Correct 506 ms 22224 KB Output is correct
10 Correct 523 ms 21880 KB Output is correct
11 Correct 530 ms 25356 KB Output is correct
12 Correct 528 ms 25356 KB Output is correct
13 Correct 509 ms 28160 KB Output is correct