oj.uz

Submission #388367

# Submission time Handle Problem Language Result Execution time Memory
388367 2021-04-11T06:26:05 Z pure_mem Synchronization (JOI13_synchronization) C++14
100 / 100
 304 ms 20220 KB 
#include <bits/stdc++.h>
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int MAXN = 100012, INF = 1e9 + 7;
const int MOD = 998244353; 

int n, m, q, sz[MAXN], parent[MAXN];
vector<int> graph[MAXN];
int hldPtr, hldCnt, hld[MAXN], hldCmp[MAXN], hldSt[MAXN], hldId[MAXN];
pair<int, int> road[MAXN];
bool isRoad[MAXN];

int t[MAXN * 4];
void upd(int v, int tl, int tr, int pos){
	if(tl > pos || pos > tr)
		return;
	if(tl == tr){
		t[v] ^= 1;
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, pos);
	upd(v * 2 + 1, tm + 1, tr, pos);
	t[v] = t[v * 2] + t[v * 2 + 1];
}
int get(int v, int tl, int tr, int pos){
	if(tl == tr){
		return tl - t[v];
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)
		return get(v * 2, tl, tm, pos);
	else{
		if(t[v] == tr - tl + 1)
			return tl - 1;
		int right = get(v * 2 + 1, tm + 1, tr, pos);
		if(right == tm && t[v * 2] == tm - tl + 1)
			right = tl - 1;
		else if(right == tm)
			right = get(v * 2, tl, tm, pos);
		return right;
	}	
}
                        
void dfs_sz(int v, int pr){
	parent[v] = pr, sz[v] = 1;
	for(int to: graph[v]){
		if(to != pr)
			dfs_sz(to, v), sz[v] += sz[to];
	}
}
void dfs(int v, int pr){
	hldPtr++;
	hld[hldPtr] = v, hldId[v] = hldPtr, hldCmp[v] = hldCnt;
	if(hldSt[hldCnt] == 0)
		hldSt[hldCnt] = v;
	int mx = 0;
	for(int to: graph[v]){
		if(to != pr && sz[mx] < sz[to])
			mx = to;
	}
	if(mx)
		dfs(mx, v);
	for(int to: graph[v]){
		if(to != pr && to != mx)
			hldCnt++, dfs(to, v);
	}
}
int get_pr(int v){
	while(v != -1){
		int vSt = hldSt[hldCmp[v]], pos = get(1, 1, n, hldId[v]);
		//cerr << pos << " " << vSt << " " << v << "\n";
		if(pos < hldId[vSt])
			v = parent[vSt];
		else
			return hld[pos];
	}
	return v;
}

int last[MAXN], answer[MAXN];
int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1;i <= n;i++)
		answer[i] = 1;
	for(int i = 1, x, y;i < n;i++){
		cin >> x >> y;
		road[i] = MP(x, y);
		graph[x].push_back(y), graph[y].push_back(x);
	}
	dfs_sz(1, -1);
	dfs(1, -1);
	for(int i = 1;i < n;i++){
		if(hldId[road[i].X] > hldId[road[i].Y])
			swap(road[i].X, road[i].Y);
	}
	for(int id;m--;){
		cin >> id, isRoad[id] ^= 1;
		if(isRoad[id]){
			int u = road[id].Y;
			upd(1, 1, n, hldId[u]);
			int v = get_pr(u);
			answer[v] += answer[u] - last[u], answer[u] = 0;
		} 
		else{
			int u = road[id].Y;
			int v = get_pr(u);
			upd(1, 1, n, hldId[u]);
			answer[u] = answer[v], last[u] = answer[v];	
		}	
	}
	for(int id;q--;){
		cin >> id;
		int v = get_pr(id);
		//cerr << v << "\n";
		cout << answer[v] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2712 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 17 ms 3660 KB Output is correct
8 Correct 17 ms 3736 KB Output is correct
9 Correct 17 ms 3660 KB Output is correct
10 Correct 216 ms 12356 KB Output is correct
11 Correct 214 ms 12484 KB Output is correct
12 Correct 154 ms 19884 KB Output is correct
13 Correct 162 ms 12872 KB Output is correct
14 Correct 144 ms 12016 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 16092 KB Output is correct
2 Correct 136 ms 16036 KB Output is correct
3 Correct 86 ms 19568 KB Output is correct
4 Correct 85 ms 19524 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 17 ms 4428 KB Output is correct
8 Correct 235 ms 20200 KB Output is correct
9 Correct 189 ms 20112 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 20116 KB Output is correct
2 Correct 118 ms 20140 KB Output is correct
3 Correct 116 ms 20168 KB Output is correct
4 Correct 118 ms 20220 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2656 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 24 ms 3780 KB Output is correct
7 Correct 304 ms 12704 KB Output is correct
8 Correct 205 ms 20116 KB Output is correct
9 Correct 229 ms 13516 KB Output is correct
10 Correct 231 ms 12792 KB Output is correct
11 Correct 160 ms 16780 KB Output is correct
12 Correct 179 ms 16784 KB Output is correct
13 Correct 139 ms 20196 KB Output is correct