답안 #388367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388367	2021-04-11T06:26:05 Z	pure_mem	동기화 (JOI13_synchronization)	C++14	100 / 100	304 ms	20220 KB

synchronization

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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