oj.uz

Submission #863692

# Submission time Handle Problem Language Result Execution time Memory
863692 2023-10-20T17:37:37 Z TAhmed33 Inside information (BOI21_servers) C++
0 / 100
 89 ms 58896 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120005;
const int MM = 15;
vector <pair <int, int>> adj[MAXN];
pair <int, int> queries[MAXN];
int t[MAXN];
int cnt = 0;
vector <int> pp[MAXN];
int dp[MM][MAXN];
int u[MM][MAXN];
int dep[MAXN];
void calc (int pos, int par) {
	for (auto j : adj[pos]) {
		if (j.first != par) {
			dep[j.first] = 1 + dep[pos];
			dp[0][j.first] = pos;
			u[0][j.first] = j.second;
			calc(j.first, pos);
		}
	}
}
int jump (int a, int b) {
	for (int i = MM - 1; i >= 0; i--) if (b & (1 << i)) a = dp[i][a];
	return a;
}
int lca (int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	b = jump(b, dep[b] - dep[a]);
	if (a == b) return a;
	for (int i = MM - 1; i >= 0; i--) {
		int x = dp[i][a], y = dp[i][b];
		if (x && y && x != y) {
			a = x; b = y;
		}
	}
	return dp[0][a];
}
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	int l = 0;
	for (int i = 1; i <= n + q - 1; i++) {
		char x;
		cin >> x;
		if (x == 'S') {
			cnt++;
			int a, b;
			cin >> a >> b;
			adj[a].push_back({b, cnt});
			adj[b].push_back({a, cnt});
		} else {
			t[++l] = cnt;
			int a, b;
			cin >> a >> b;
			queries[l] = {a, b};
		}
	}
	calc(1, 0);
	for (int i = 1; i < MM; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
	for (int i = 1; i <= l; i++) {
		vector <int> pp;
		int x = lca(queries[i].first, queries[i].second);
		assert(x >= 1 && x <= n);
		int a = queries[i].first, b = queries[i].second;
		swap(a, b);
		vector <int> d;
		while (a != x) {
			d.push_back(u[0][a]);
			a = dp[0][a];
			assert(a);
		}
		vector <int> g;
		while (b != x) {
			g.push_back(u[0][b]);
			b = dp[0][b];
			assert(b);
		}
		reverse(g.begin(), g.end());
		for (auto j : g) d.push_back(j);
		bool flag = 1;
		for (int j = 1; j < (int)d.size(); j++) flag &= d[j] >= d[j - 1];
		flag &= (d.back() <= t[i]);
		cout << (flag ? "yes\n" : "no\n");
	}
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 18000 KB Output is correct
2 Runtime error 31 ms 35872 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 18000 KB Output is correct
2 Runtime error 31 ms 35872 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17944 KB Output is correct
2 Runtime error 59 ms 45560 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17944 KB Output is correct
2 Runtime error 59 ms 45560 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18100 KB Output is correct
2 Runtime error 79 ms 58896 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18100 KB Output is correct
2 Runtime error 79 ms 58896 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18016 KB Output is correct
2 Runtime error 63 ms 45572 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18016 KB Output is correct
2 Runtime error 63 ms 45572 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 18000 KB Output is correct
2 Runtime error 89 ms 58740 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 18000 KB Output is correct
2 Runtime error 89 ms 58740 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17936 KB Output is correct
2 Runtime error 45 ms 35924 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17936 KB Output is correct
2 Runtime error 45 ms 35924 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -