Submission #409018

#	Time	Username	Problem	Language	Result	Execution time	Memory
409018		Kevin_Zhang_TW	Inside information (BOI21_servers)	C++17	100 / 100	512 ms	42052 KiB

servers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto l, auto r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9;

//       res == -10 ? not a query 
//       res == -2 ? no, it doesn't have it
//		 res == -1 ? yes, it has it
//		 res >= 0 ? how many is it
int n, q, res[MAX_N];

//        time, id
vector<pair<int,int>> edge[MAX_N];
//   given time, id how many has this
vector<int> qcnt[MAX_N];
//   given time, whether x has it
vector<pair<int,int>> qif[MAX_N];

bool ban[MAX_N];
int sz[MAX_N], bitv[MAX_N], in_time[MAX_N];
void add(int i, int d) {
	for (;i <= n+q;i += i&-i)
		bitv[i] += d;
}
int qry(int i) {
	int res = 0;
	for (;i;i ^= i&-i)
		res += bitv[i];
	return res;
}
void clean_edge(int x) {
	int sz = 0;
	for (auto [t, u] : edge[x]) if (!ban[u]) edge[x][sz++] = {t, u};
	edge[x].resize(sz);
}

int dfs_sz(int x, int lst) {
	sz[x] = 1;
	for (auto [t, u] : edge[x]) if (!ban[u] && u != lst)
		sz[x] += dfs_sz(u, x);
	return sz[x];
}
int dfs_cen(int x, int allsz, int lst) {
	for (auto [t, u] : edge[x]) if (!ban[u] && u != lst)
		if (sz[u] * 2 > allsz) return dfs_cen(u, allsz, x);
	return x;
}

void dfs_in(int x, int lst_v, int lst) {
	in_time[x] = lst_v;
	add(lst_v, 1);
	for (auto [t, u] : edge[x]) if (u != lst && !ban[u])
		if (t >= lst_v)
			dfs_in(u, t, x);
}
void dfs_out(int x, int lst_v, int lst) {
	in_time[x] = inf;
	add(lst_v, -1);
	for (auto [t, u] : edge[x]) if (u != lst && !ban[u])
		if (t >= lst_v)
			dfs_out(u, t, x);
}

void do_ans(int u) {
	for (int t : qcnt[u]) {
		DE(t, n + q);
		res[t] += qry(t);
	}
	for (auto [t, x] : qif[u]) {
		if (in_time[x] <= t)
			res[t] = -1;
	}
}
void dfs_solve(int x, int lst_v, int lst) {
	do_ans(x);
	for (auto [t, u] : edge[x]) if (!ban[u] && u != lst) {
		if (t > lst_v) continue;
		dfs_solve(u, t, x);
	}
}

void solve(int o = 1) {
	if (ban[o]) return;
	dfs_sz(o, o);
	int cen = dfs_cen(o, sz[o], o);
	clean_edge(cen);
	sort(AI(edge[cen]));

	dfs_in(cen, 1, cen);

	do_ans(cen);

	for (auto [t, u] : edge[cen]) {
		dfs_out(u, t, cen);
		add(in_time[cen], -1);
		add(in_time[cen] = t, 1);
		dfs_solve(u, t, cen);
	}
	ban[cen] = true;

	add(in_time[cen], -1);
	in_time[cen] = inf;

	for (auto [t, x] : edge[cen])
		solve(x);
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	for (int i = 1;i < n+q;++i) {
		char c;
		int a, b;
		cin >> c;
		if (c == 'C') {
			cin >> a;
			qcnt[a].pb(i);
			res[i] = 0;
			continue;
		}
		cin >> a >> b;
		if (c == 'S') {
			edge[a].pb(i, b);
			edge[b].pb(i, a);
			res[i] = -10;
		}
		if (c == 'Q') {
			res[i] = -2;
			qif[b].pb(i, a);
		}
		DE(i, res[i]);

	}

	fill(in_time, in_time + n + 1, inf);

	solve();

	for (int i = 1;i < n + q;++i) {
		if (res[i] == -10) continue;
		if (res[i] == -2) {
			cout << "no\n";
			continue;
		}
		if (res[i] == -1) {
			cout << "yes\n";
			continue;
		}
		cout << res[i] << '\n';
	}
}

Compilation message (stderr)

servers.cpp: In function 'void do_ans(int)':
servers.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
servers.cpp:80:3: note: in expansion of macro 'DE'
   80 |   DE(t, n + q);
      |   ^~
servers.cpp: In function 'int32_t main()':
servers.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
servers.cpp:145:3: note: in expansion of macro 'DE'
  145 |   DE(i, res[i]);
      |   ^~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5