Submission #1304514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304514		hoa208	Synchronization (JOI13_synchronization)	C++20	100 / 100	142 ms	19080 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------

ll n, m, q;
const ll N = 2e5 + 10;
vector<ll> g[N];
struct segtree {
	ll mx;
} st[4 * N];
ll arr[N], in[N], en[N];
ll val[N], last[N], par[N];
ll timedfs;
void dfs(ll u, ll p) {
	in[u] = ++timedfs;
	arr[timedfs] = u;
	for(auto v : g[u]) {
		if(v == p) continue;
		par[v] = u;
		dfs(v, u);
	}
	en[u] = timedfs;
}
void update(ll u, ll val, ll id = 1, ll l = 1, ll r = n) {
	if(u < l || u > r) return;
	if(l == r) {
		st[id].mx = val;
		return;
	}
	ll mid = l + r >> 1;
	update(u, val, id << 1, l, mid);
	update(u, val, id << 1 | 1, mid + 1, r);
	st[id].mx = max(st[id << 1].mx, st[id << 1 | 1].mx);
}
void build(ll id = 1, ll l = 1, ll r = n) {
	if(l == r) {
		st[id].mx = en[arr[l]];
		return;
	}
	ll mid = l + r >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	st[id].mx = max(st[id << 1].mx, st[id << 1 | 1].mx);
}
ll walk(ll w, ll u, ll id = 1, ll l = 1, ll r = n) {
	if(st[id].mx < w) return 0;
	if(l == r) return arr[l];
	ll mid = l + r >> 1;
	ll res = 0;
	if(u >= mid + 1) {
		res = walk(w, u, id << 1 | 1, mid + 1, r);
	}
	if(res) return res;
	return walk(w, u, id << 1, l, mid);
}
pa ed[N];
bool dx[N];
ll findset(ll u) {
	return walk(en[u], in[u]);
}
void hbmt() {
	cin >> n >> m >> q;
	FOR(i, 1, n - 1) {
		ll u, v;
		cin >> u >> v;
		ed[i] = {u, v};
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	build();
	FOR(i, 1, n) {
		val[i] = 1;
	}
	FOR(i, 1, m) {
		ll id;
		cin >> id;
		ll u = ed[id].fi, v = ed[id].se;
		if(par[v] != u) swap(u, v);
		if(dx[id] == 0) { // add
			u = findset(u);
			assert(u != 0);
			val[u] += val[v] - last[v];
			update(in[v], 0);
			dx[id] = 1;
		}
		else {
			u = findset(u);
			assert(u != 0);
			val[v] = val[u];
			last[v] = val[v];
			update(in[v], en[v]);
			dx[id] = 0;
		}
	}
	FOR(i, 1, q) {
		ll c;
		cin >> c;
		c = findset(c);
		assert(c != 0);
		cout << val[c] << '\n';
	}
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	#define NAME "hbmt"
	if(fopen(NAME".inp", "r")) {
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
	}
	
	//int t;cin>>t;while(t--)
	hbmt();
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen(NAME".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:122:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |                 freopen(NAME".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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