제출 #349055

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

synchronization

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

vi G[N];
int p[N][20], on[N], tin[N], tout[N], tt, ans[N], last[N];

void dfs(int u, int pa = 0) {
	tin[u] = ++tt;
	p[u][0] = pa;
	for(int i = 1; i < 20; i++)
		p[u][i] = p[p[u][i - 1]][i - 1];
	for(int v:G[u]) if(v != pa)
		dfs(v, u);
	tout[u] = tt;
}

int bit[N];

void add(int pos, int val) {
	for(; pos < N; pos += pos & -pos)
		bit[pos] += val;
}

void add(int l, int r, int val) {
	add(l, val);
	add(r + 1, -val);
}

int qry(int pos) {
	int res = 0;
	for(; pos; pos -= pos & -pos)
		res += bit[pos];
	return res;
}

int find(int u) {
	int tt = qry(tin[u]);
	for(int j = 19; j >= 0; j--)
		if(p[u][j] && qry(tin[p[u][j]]) == tt)
			u = p[u][j];
	return u;
}

signed main()
{
	IO_OP;

	int n, m, q;
	cin >> n >> m >> q;
	vi u(m), v(m);
	for(int i = 0; i < n - 1; i++) {
		cin >> u[i] >> v[i];
		G[u[i]].PB(v[i]);
		G[v[i]].PB(u[i]);
	}
	dfs(1);
	for(int i = 1; i <= n; i++) {
		add(tin[i], tout[i], 1);
		ans[i] = 1;
	}

	while(m--) {
		int d;
		cin >> d;
		d--;
		int x = (p[u[d]][0] == v[d] ? u[d] : v[d]);
		if(on[d]) { // cut
			int y = find(x);
			assert(x != y);
			last[x] = ans[x] = ans[y];
			add(tin[x], tout[x], 1);
		} else { // link
			int y = find(p[x][0]);
			int nw = ans[x] + ans[y] - last[x];
			ans[y] = nw;
			add(tin[x], tout[x], -1);
		}
		on[d] ^= 1;
	}
	while(q--) {
		int u;
		cin >> u;
		cout << ans[find(u)] << '\n';
	}


}

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