oj.uz

Submission #403815

# Submission time Handle Problem Language Result Execution time Memory
403815 2021-05-13T13:35:41 Z abdzag Inside information (BOI21_servers) C++17
7.5 / 100
 376 ms 71208 KB 
#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);
vector<ll> depth(2e5, -1);
vector<pair<ll, ll>> parent(2e5);
vector<vector<ll>> parents(20, vector<ll>(2e5));
ll Root = 1;
vector<vector<ll>> children(2e5);
pair<ll, ll> lca(ll a, ll b, vector<vector<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];
		diff--;
	}
	ll mx = 0;
	rrep(i, 19, -1) {
		if (diff & (1 << i)) {
			if (parents[i][a] == b) {
				return make_pair(a, a);
			}
			a = parents[i][a];
		}
	}
	rrep(i, 19, -1) {
		if (parents[i][b] != parents[i][b]) {
			a = parents[i][a];
			b = parents[i][b];
		}
	}
	if (swaped)swap(a, b);
	return make_pair(a, b);
}
void dfs(ll cur, ll last) {
	if (cur != Root) {
		if (last == Root)lds[cur] = ++lis[cur];
		else if (parent[cur].second < parent[last].second) {
			lis[cur] = lis[last] + 1;
			lds[cur] = 1;
		}
		else {
			lds[cur] = lds[last] + 1;
			lis[cur] = 1;
		}
	}
	trav(a, children[cur])dfs(a, cur);
}
int main() {
	cin.sync_with_stdio(false);
	ll n, Q;
	cin >> n >> Q;
	vector<vector<pair<ll, ll>>> g(n + 1);
	vector<pair<pair<ll, ll>, pair<ll, ll>>> queries;
	ll counter = 0;
	rep(i, 0, n + Q - 1) {
		char c;
		ll a, b;
		cin >> c;
		if (c == 'S') {
			cin >> a >> b;
			g[a].emplace_back(b, ++counter);
			g[b].emplace_back(a, counter);
		}
		else if (c == 'Q') {
			cin >> a >> b;
			queries.emplace_back(make_pair(0, counter), make_pair(a, b));
		}
		else {
			cin >> a;
			queries.emplace_back(make_pair(1, counter), make_pair(a, b));
		}
	}

	parent[Root] = make_pair(Root, 0);
	queue<ll> q;
	q.push(Root);
	depth[Root] = 0;
	while (!q.empty()) {
		ll cur = q.front();
		q.pop();
		rep(i, 0, g[cur].size()) {
			ll v = g[cur][i].first;
			if (depth[v] == -1) {
				depth[v] = depth[cur] + 1;
				q.push(v);
			}
		}
	}
	q.push(Root);
	while (!q.empty()) {
		ll cur = q.front();
		q.pop();
		rep(i, 0, g[cur].size()) {
			if (!parent[g[cur][i].first].first) {
				parent[g[cur][i].first] = make_pair(cur, g[cur][i].second);
				q.push(g[cur][i].first);
				children[cur].push_back(g[cur][i].first);
			}
		}
	}
	rep(i, 1, n + 1)parents[0][i] = parent[i].first;
	rep(i, 1, 20) {
		rep(j, 1, n + 1) {
			parents[i][j] = parents[i - 1][parents[i - 1][j]];
		}
	}
	dfs(1, 1);
	trav(query, queries) {
		if (query.first.first == 0) {
			ll a = query.second.second;//want to know whether chunk of data a is in server b
			ll b = query.second.first;
			pair<ll, ll> val = lca(a, b, parents); //returns last node before lca for a and b respectively
			if (a == b) {
				cout << "yes" << endl;
				continue;
			}
			if (parent[val.first].second <= parent[val.second].second) {
				ll LCA = parent[val.first].first;
				bool aactive = parent[val.first].second <= query.first.second;
				bool bactive = parent[b].second <= query.first.second;
				if (b == LCA)bactive = 1;
				if (depth[a] - lis[a] <= depth[LCA] && depth[b] - lds[b] <= depth[LCA] && aactive && bactive)cout << "yes" << endl;
				else cout << "no" << endl;
			}
			else cout << "no" << endl;
		}
	}
	return 0;
}

Compilation message

servers.cpp: In function 'std::pair<long long int, long long int> lca(ll, ll, std::vector<std::vector<long long int> >&)':
servers.cpp:30:5: warning: unused variable 'mx' [-Wunused-variable]
   30 |  ll mx = 0;
      |     ^~

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 53424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 53424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 237 ms 53416 KB Output is correct
2 Correct 317 ms 64552 KB Output is correct
3 Correct 338 ms 64576 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 237 ms 53416 KB Output is correct
2 Correct 317 ms 64552 KB Output is correct
3 Correct 338 ms 64576 KB Output is correct
4 Incorrect 231 ms 54264 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 53476 KB Output is correct
2 Correct 357 ms 71076 KB Output is correct
3 Correct 376 ms 71168 KB Output is correct
4 Correct 363 ms 70680 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 53476 KB Output is correct
2 Correct 357 ms 71076 KB Output is correct
3 Correct 376 ms 71168 KB Output is correct
4 Correct 363 ms 70680 KB Output is correct
5 Incorrect 230 ms 54436 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 53552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 53552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 241 ms 53424 KB Output is correct
2 Correct 366 ms 71160 KB Output is correct
3 Correct 374 ms 71208 KB Output is correct
4 Correct 365 ms 70692 KB Output is correct
5 Incorrect 245 ms 54380 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 241 ms 53424 KB Output is correct
2 Correct 366 ms 71160 KB Output is correct
3 Correct 374 ms 71208 KB Output is correct
4 Correct 365 ms 70692 KB Output is correct
5 Incorrect 245 ms 54380 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 53392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 53392 KB Output isn't correct
2 Halted 0 ms 0 KB -