//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const int L = 20;
struct path {
bool asc, dec;
int min, max;
};
path combine(path a, path b) {
bool asc, dec;
if (a.min == -1) return b;
if (b.min == -1) return a;
asc = a.asc && b.asc && a.max < b.min;
dec = a.dec && b.dec && a.min > b.max;
return {asc, dec, min(a.min, b.min), max(a.max, b.max)};
}
ve<int> D;
ve<ve<int>> A;
ve<ve<pii>> G;
ve<ve<path>> X;
void f(int u, int p, int s, int d) {
int a = p;
path x = {true, true, s, s};
for (int i = 0; i < L; i++) {
A[u][i] = a;
X[u][i] = x;
if (a != -1) {
x = combine(x, X[a][i]);
a = A[a][i];
}
}
D[u] = d;
for (pii e : G[u]) {
int v, t;
tie(v, t) = e;
if (v != p) f(v, u, t, d + 1);
}
}
int lca(int a, int b) {
bool swp = false;
if (D[a] < D[b]) {
swap(a, b);
swp = true;
}
path xa = {true, true, -1, -1};
path xb = {true, true, -1, -1};
for (int i = L - 1; i >= 0; i--) {
if (D[a] - (1 << i) >= D[b]) {
xa = combine(xa, X[a][i]);
a = A[a][i];
}
}
if (a != b) {
for (int i = L - 1; i >= 0; i--) {
if (A[a][i] != A[b][i]) {
xa = combine(xa, X[a][i]);
a = A[a][i];
xb = combine(xb, X[b][i]);
b = A[b][i];
}
}
xa = combine(xa, X[a][0]);
xb = combine(xb, X[b][0]);
}
if (swp) swap(xa, xb);
swap(xb.asc, xb.dec);
path x = combine(xa, xb);
if (x.asc) return x.max;
else return INF;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k, a, b, d, t;
ve<tuple<int, int, int, int>> Q;
ve<int> Z, Left, Right;
cin >> n >> k;
D = ve<int>(n);
A = ve<ve<int>>(n, ve<int>(L));
G = ve<ve<pii>>(n);
X = ve<ve<path>>(n, ve<path>(L));
Z = ve<int>(n - 1);
Left = ve<int>(n);
Right = ve<int>(n);
t = 0;
for (int i = 0; i < n + k - 1; i++) {
char c;
cin >> c;
if (c == 'S') {
cin >> a >> b;
a--;
b--;
t++;
G[a].push_back({b, t});
G[b].push_back({a, t});
Z[min(a, b)] = t;
}
else if (c == 'Q') {
cin >> a >> d;
a--;
d--;
Q.push_back({1, a, d, t});
}
else {
cin >> d;
d--;
Q.push_back({2, d, t, 0});
}
}
f(0, -1, -1, 0);
int prev = INF;
int cnt = 0;
Left[0] = 0;
for (int i = 0; i < n - 1; i++) {
if (Z[i] < prev) cnt++;
else cnt = 1;
Left[i + 1] = cnt;
prev = Z[i];
}
prev = INF;
cnt = 0;
Right[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
if (Z[i] < prev) cnt++;
else cnt = 1;
Right[i] = cnt;
prev = Z[i];
}
cout << " ";
for (int i = 0; i < n - 1; i++) cout << Z[i] << " ";
cout << endl;
for (int i = 0; i < n; i++) cout << Left[i] << " ";
cout << endl;
for (int i = 0; i < n; i++) cout << Right[i] << " ";
cout << endl;
for (int i = 0; i < k; i++) {
if (get<0>(Q[i]) == 1) {
tie(ignore, a, d, t) = Q[i];
int r = lca(d, a);
if (r <= t) cout << "yes" << endl;
else cout << "no" << endl;
}
else {
tie(ignore, d, t, ignore) = Q[i];
int ans = 1;
cout << d << " " << t << endl;
if (Left[d] != 0) {
auto y = Z.begin() + d;
auto x = y - Left[d];
auto it = lower_bound(x, y, t, greater<int>());
int inc = (int)distance(it, y);
ans += inc;
}
if (Right[d] != 0) {
auto x = Z.begin() + d;
auto y = x + Right[d];
auto it = lower_bound(x, y, t);
int inc = (int)distance(x, it);
ans += inc;
}
cout << ans << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
3296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
3296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
3484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
3484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
245 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
245 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
3444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
3444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
3372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
3372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
