Submission #659810

#	Time	Username	Problem	Language	Result	Execution time	Memory
659810		NothingXD	Inside information (BOI21_servers)	C++17	100 / 100	537 ms	44468 KiB

servers

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef __uint128_t L;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 10;

int n, q, N, f[maxn], sz[maxn], ans[maxn];
pii mn[maxn], mx[maxn];
vector<pii> g[maxn];
bool vis[maxn], mark[maxn], flg[maxn];
vector<int> going, tmp;
vector<pii> Q1[maxn];
vector<int> Q2[maxn];

void add(int idx, int x){
	idx++;
	for (; idx <= N+1; idx += idx & -idx) f[idx] += x;
}

int get(int idx){
	idx++;
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

void dfs(int v, int p = -1){
	going.push_back(v);
	mn[v] = {N, 0};
	mx[v] = {0, 0};
	sz[v] = 1;
	for (auto [u, w]: g[v]){
		if (u != p && !vis[u]){
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
}

int getcen(int v, int n, int p = -1){
	for (auto [u, w]: g[v]){
		if (!vis[u] && u != p && sz[u] * 2 > n) return getcen(u, n, v);
	}
	return v;
}

void getmn(int v, pii W, int p = -1){
	mn[v] = W;
	for (auto [u, w]: g[v]){
		if (!vis[u] && u != p && w < W.S) getmn(u, {W.F, w}, v);
	}
}

void getmx(int v, pii W, int p = -1){
	mx[v] = W;
	for (auto [u, w]: g[v]){
		if (!vis[u] && u != p && w > W.S) getmx(u, {W.F, w}, v); 
	}
}

bool cmp(int x, int y){
	return mx[x].F > mx[y].F;
}

bool cmp2(int x, int y){
	return mn[x].F > mn[y].F;
}

void solve(int v){
//	debug(v);
	going.clear();
	dfs(v);
	for (auto x: going) flg[x] = true;
	v = getcen(v, sz[v]);
	vis[v] = true;
	mx[v] = {N, 0};
	mn[v] = {0, 0};
//	debug(v);
	for (auto [u, w]: g[v]){
		if (vis[u]) continue;
		getmn(u, {w, w});
		getmx(u, {w, w});
	}
/*	for (auto u: going){
		debug(u, mn[u].F, mn[u].S, mx[u].F, mx[u].S);
	}*/
	for (auto u: going){
		for (auto [t, x]: Q1[u]){
			if (!flg[x]) continue;
			if (mn[u].F > t) continue;
			if (mn[u].F < mx[x].F &&  mx[x].S <= t){
				ans[t] = 1;
			}
		}
	}
	tmp = going;
	sort(all(going), cmp);
	sort(all(tmp), cmp2);
	int ptr = 0;
	for (int i = 0; i < tmp.size(); i++){
		int x = tmp[i];
		while(ptr != going.size() && mx[going[ptr]].F > mn[x].F){
	//		debug(going[ptr], mx[going[ptr]].S);
			add(mx[going[ptr]].S, 1);
			ptr++;
		}
		for (auto t: Q2[x]){
			if (mn[x].F > t) continue;
	//		debug(t, get(t));
			ans[t] += get(t);
		}
	}
	for (int i = 0; i < ptr; i++){
		add(mx[going[i]].S, -1);
	}
	for (auto x: going) flg[x] = false;
	for (auto [u, w]: g[v]){
		if (!vis[u]) solve(u);
	}
}

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

	memset(ans, -1, sizeof ans);

	cin >> n >> q;
	N = n+q;

	for (int i = 1; i < N; i++){
		char t; cin >> t;
		if (t == 'S'){
			int u, v; cin >> u >> v;
			g[u].push_back({v, i});
			g[v].push_back({u, i});
		}
		else if (t == 'Q'){
			int x, y; cin >> x >> y;
			Q1[y].push_back({i, x});
			ans[i] = 0;
			mark[i] = true;
		}
		else{
			int x; cin >> x;
			Q2[x].push_back(i);
			ans[i] = 0;
		}
	}


	solve(1);

	int cnt = 0;

	for (int i = 1; i < N; i++){
		if (ans[i] == -1) continue;
		cnt++;
		assert(cnt <= q);
		if (mark[i]){
			cout << (ans[i]? "yes": "no");
		}
		else{
			cout << ans[i];
		}
		cout << "\n";
	}

	return 0;
}

Compilation message (stderr)

servers.cpp: In function 'void solve(int)':
servers.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for (int i = 0; i < tmp.size(); i++){
      |                  ~~^~~~~~~~~~~~
servers.cpp:124:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   while(ptr != going.size() && mx[going[ptr]].F > mn[x].F){
      |         ~~~~^~~~~~~~~~~~~~~

• 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