oj.uz

Submission #403843

# Submission time Handle Problem Language Result Execution time Memory
403843 2021-05-13T14:11:08 Z abdzag Inside information (BOI21_servers) C++17
50 / 100
 718 ms 71068 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][a]) {
			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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 259 ms 53492 KB Output is correct
2 Correct 342 ms 54880 KB Output is correct
3 Correct 368 ms 55084 KB Output is correct
4 Correct 319 ms 54960 KB Output is correct
5 Correct 325 ms 55212 KB Output is correct
6 Correct 315 ms 55040 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 259 ms 53492 KB Output is correct
2 Correct 342 ms 54880 KB Output is correct
3 Correct 368 ms 55084 KB Output is correct
4 Correct 319 ms 54960 KB Output is correct
5 Correct 325 ms 55212 KB Output is correct
6 Correct 315 ms 55040 KB Output is correct
7 Incorrect 275 ms 53588 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 278 ms 53476 KB Output is correct
2 Correct 701 ms 62676 KB Output is correct
3 Correct 694 ms 62656 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 278 ms 53476 KB Output is correct
2 Correct 701 ms 62676 KB Output is correct
3 Correct 694 ms 62656 KB Output is correct
4 Incorrect 256 ms 53512 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 268 ms 53560 KB Output is correct
2 Correct 492 ms 67968 KB Output is correct
3 Correct 452 ms 67980 KB Output is correct
4 Correct 383 ms 67660 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 53560 KB Output is correct
2 Correct 492 ms 67968 KB Output is correct
3 Correct 452 ms 67980 KB Output is correct
4 Correct 383 ms 67660 KB Output is correct
5 Incorrect 233 ms 53520 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 53448 KB Output is correct
2 Correct 572 ms 66772 KB Output is correct
3 Correct 484 ms 66768 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 53448 KB Output is correct
2 Correct 572 ms 66772 KB Output is correct
3 Correct 484 ms 66768 KB Output is correct
4 Incorrect 256 ms 54384 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 240 ms 53424 KB Output is correct
2 Correct 437 ms 68052 KB Output is correct
3 Correct 453 ms 68056 KB Output is correct
4 Correct 377 ms 67732 KB Output is correct
5 Correct 265 ms 53616 KB Output is correct
6 Correct 540 ms 66724 KB Output is correct
7 Correct 486 ms 66752 KB Output is correct
8 Correct 630 ms 67052 KB Output is correct
9 Correct 616 ms 66624 KB Output is correct
10 Correct 576 ms 67456 KB Output is correct
11 Correct 608 ms 67168 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 240 ms 53424 KB Output is correct
2 Correct 437 ms 68052 KB Output is correct
3 Correct 453 ms 68056 KB Output is correct
4 Correct 377 ms 67732 KB Output is correct
5 Correct 265 ms 53616 KB Output is correct
6 Correct 540 ms 66724 KB Output is correct
7 Correct 486 ms 66752 KB Output is correct
8 Correct 630 ms 67052 KB Output is correct
9 Correct 616 ms 66624 KB Output is correct
10 Correct 576 ms 67456 KB Output is correct
11 Correct 608 ms 67168 KB Output is correct
12 Incorrect 233 ms 54336 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 261 ms 53432 KB Output is correct
2 Correct 321 ms 54956 KB Output is correct
3 Correct 307 ms 55036 KB Output is correct
4 Correct 303 ms 55088 KB Output is correct
5 Correct 261 ms 55168 KB Output is correct
6 Correct 305 ms 54992 KB Output is correct
7 Correct 336 ms 54308 KB Output is correct
8 Correct 710 ms 65248 KB Output is correct
9 Correct 703 ms 65340 KB Output is correct
10 Correct 272 ms 54336 KB Output is correct
11 Correct 534 ms 71068 KB Output is correct
12 Correct 521 ms 71056 KB Output is correct
13 Correct 447 ms 70676 KB Output is correct
14 Correct 279 ms 54312 KB Output is correct
15 Correct 581 ms 66676 KB Output is correct
16 Correct 619 ms 66792 KB Output is correct
17 Correct 658 ms 66984 KB Output is correct
18 Correct 592 ms 66460 KB Output is correct
19 Correct 593 ms 67484 KB Output is correct
20 Correct 718 ms 67108 KB Output is correct
21 Correct 704 ms 65300 KB Output is correct
22 Correct 703 ms 65320 KB Output is correct
23 Correct 660 ms 65484 KB Output is correct
24 Correct 670 ms 65556 KB Output is correct
25 Correct 616 ms 67204 KB Output is correct
26 Correct 558 ms 66156 KB Output is correct
27 Correct 491 ms 66076 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 261 ms 53432 KB Output is correct
2 Correct 321 ms 54956 KB Output is correct
3 Correct 307 ms 55036 KB Output is correct
4 Correct 303 ms 55088 KB Output is correct
5 Correct 261 ms 55168 KB Output is correct
6 Correct 305 ms 54992 KB Output is correct
7 Correct 336 ms 54308 KB Output is correct
8 Correct 710 ms 65248 KB Output is correct
9 Correct 703 ms 65340 KB Output is correct
10 Correct 272 ms 54336 KB Output is correct
11 Correct 534 ms 71068 KB Output is correct
12 Correct 521 ms 71056 KB Output is correct
13 Correct 447 ms 70676 KB Output is correct
14 Correct 279 ms 54312 KB Output is correct
15 Correct 581 ms 66676 KB Output is correct
16 Correct 619 ms 66792 KB Output is correct
17 Correct 658 ms 66984 KB Output is correct
18 Correct 592 ms 66460 KB Output is correct
19 Correct 593 ms 67484 KB Output is correct
20 Correct 718 ms 67108 KB Output is correct
21 Correct 704 ms 65300 KB Output is correct
22 Correct 703 ms 65320 KB Output is correct
23 Correct 660 ms 65484 KB Output is correct
24 Correct 670 ms 65556 KB Output is correct
25 Correct 616 ms 67204 KB Output is correct
26 Correct 558 ms 66156 KB Output is correct
27 Correct 491 ms 66076 KB Output is correct
28 Incorrect 278 ms 54324 KB Extra information in the output file
29 Halted 0 ms 0 KB -