제출 #388367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388367		pure_mem	동기화 (JOI13_synchronization)	C++14	100 / 100	304 ms	20220 KiB

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