Submission #403277

#TimeUsernameProblemLanguageResultExecution timeMemory
403277abdzagInside information (BOI21_servers)C++17
2.50 / 100
354 ms88872 KiB
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define  sz(a) a.size()
typedef long double ld;
using namespace std;
const long long inf = 1e15;
typedef long long ll;
typedef unsigned long long ull;
vector<ll> lis(2e5);
vector<ll> lds(2e5);
vector<ll> ris(2e5);
vector<ll> rds(2e5);
void Uinitate(vector<ll>& p) {
	rep(i, 0, p.size())p[i] = i;
}
ll UfindSet(ll cur, vector<ll>& p) {
	if (p[cur] == cur)return cur;
	return p[cur] = UfindSet(p[cur], p);
}
void Ujoin(ll i, ll j, vector<ll>& p, vector<ll>& r) {
	ll si = UfindSet(i, p);
	ll sj = UfindSet(j, p);
	if (si == sj)return;
	if (r[si] > r[sj])swap(sj, si);
	p[si] = sj;
	r[sj]++;
}
vector<ll> depth(2e5, -1);
pair<pair<ll, ll>, ll> lca(ll a, ll b, vector<vector<pair<ll, ll>>>& parents) {
	bool swaped = depth[a] < depth[b];
	if (depth[a] < depth[b])swap(a, b);
	ll diff = depth[a] - depth[b];
	if (diff % 2 == 0 && diff) {
		a = parents[0][a].first;
		diff--;
	}
	ll mx = 0;
	rrep(i, 19, -1) {
		if (diff & (1 << i)) {
			mx = max(mx, parents[i][a].second);
			if (parents[i][a].first == b) {
				return make_pair(make_pair(a, a), mx);
			}
			a = parents[i][a].first;
		}
	}
	rrep(i, 19, -1) {
		if (parents[i][b] != parents[i][b]) {
			a = parents[i][a].first;
			b = parents[i][b].first;
			mx = max(mx, parents[i][a].second);
			mx = max(mx, parents[i][b].second);
		}
	}
	if (swaped)swap(a, b);
	return make_pair(make_pair(a, b), mx);
}
int main() {
	cin.sync_with_stdio(false);
	ll n, Q;
	cin >> n >> Q;
	vector<vector<pair<ll, ll>>> g(n + 1);
	vector<bitset<5000>> v(n + 1);
	rep(i, 1, n + 1)v[i][i] = 1;
	ll counter = 0;
	rep(i, 0, n + Q - 1) {
		char c;
		ll a, b;
		cin >> c;
		if (c == 'S') {
			cin >> a >> b;
			v[a] |= v[b];
			v[b] |= v[a];
		}
		else if (c == 'Q') {
			cin >> a >> b;
			cout << (v[a][b] ? "yes\n" : "no\n");
		}
		else {
			cin >> a;
		}
	}

	return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:69:5: warning: unused variable 'counter' [-Wunused-variable]
   69 |  ll counter = 0;
      |     ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...