#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int inf = int(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#define _LOCAL _DEBUG
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
const int maxn = int(1.5e5);
int tin[maxn];
int tout[maxn];
int timer = 0;
int up[maxn][18];
int upincreasing[maxn][18];
int updecreasing[maxn][18];
int upmax[maxn][18];
int upv[maxn];
void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
tin[u] = timer++;
up[u][0] = p;
upmax[u][0] = upv[u];
upincreasing[u][0] = upmax[u][0] < upmax[p][0] || p==0 || u==0;
updecreasing[u][0] = upmax[u][0] > upmax[p][0] || p==0 || u==0;
repp(d,1,18)
{
int mid = up[u][d - 1];
up[u][d] = up[mid][d - 1];
upmax[u][d] = max(upmax[u][d - 1], upmax[mid][d - 1]);
upincreasing[u][d] = upincreasing[u][d - 1] && upincreasing[mid][d - 1] && (upmax[mid][0] < upmax[up[mid][0]][0] || up[mid][0] ==0||mid==0);
updecreasing[u][d] = updecreasing[u][d - 1] && updecreasing[mid][d - 1] && (upmax[mid][0] > upmax[up[mid][0]][0] || up[mid][0] ==0||mid==0);
}
repe(e, edges[u]) if (e.first != p)
{
upv[e.first] = e.second;
dfs(e.first, u, p1, _p2, edges);
}
tout[u] = timer++;
}
bool isancestor(int a, int b)
{
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int pathmax(int a, int b)
{
if (isancestor(a, b)) return -1;
int ret = -1;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[a][d], b))
{
ret = max(ret, upmax[a][d]);
a = up[a][d];
}
}
return max(ret, upmax[a][0]);
}
signed main()
{
fast();
//ifstream in("C:\\Users\\Matis\\desktop\\comp_prog\\x64\\debug\\in.txt");
//cin.rdbuf(in.rdbuf());
int n, q;
cin >> n >> q;
vvi queries;
int t = 0;
vector<vector<p2>> edges(n);
rep(i, n + q - 1)
{
char c;
cin >> c;
if (c=='S')
{
int a, b;
cin >> a >> b;
a--; b--;
edges[a].emplace_back(b, t);
edges[b].emplace_back(a, t);
t++;
}
else if (c=='Q')
{
int a, b;
cin >> a >> b;
a--; b--;
queries.push_back({ 0, b, a, t-1 });
}
else
{
int c;
cin >> c;
c--;
queries.push_back({ 1, c, -1, t-1 });
}
}
dfs(0, 0, -1, -1, edges);
auto getmax = [&](int a, int b)
{
return max(pathmax(a, b), pathmax(b, a));
};
auto pathgood = [&](int a, int b, int t)
{
if (getmax(a, b) > t) return false;
// all edges <= t
// from b->lca increasing
// from a->lca decreasing
bool good = 1;
int u = b;
int prev = inf;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[u][d],a))
{
good &= updecreasing[u][d];
u = up[u][d];
}
}
if (!isancestor(u,a))
{
prev = upmax[u][0];
}
u = a;
int v = -1;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[u][d], b))
{
good &= upincreasing[u][d];
u = up[u][d];
}
}
if (!isancestor(u, b))
{
v = upmax[u][0];
}
return good && (v < prev);
};
repe(q, queries)
{
int type=q[0], a=q[1], b=q[2], t=q[3];
if (type==0)
{
cout << (pathgood(a, b, t) ? "yes" : "no") << "\n";
}
else
{
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
18176 KB |
Output is correct |
2 |
Correct |
46 ms |
20948 KB |
Output is correct |
3 |
Correct |
45 ms |
20892 KB |
Output is correct |
4 |
Correct |
51 ms |
20996 KB |
Output is correct |
5 |
Correct |
62 ms |
21348 KB |
Output is correct |
6 |
Correct |
49 ms |
20992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
18176 KB |
Output is correct |
2 |
Correct |
46 ms |
20948 KB |
Output is correct |
3 |
Correct |
45 ms |
20892 KB |
Output is correct |
4 |
Correct |
51 ms |
20996 KB |
Output is correct |
5 |
Correct |
62 ms |
21348 KB |
Output is correct |
6 |
Correct |
49 ms |
20992 KB |
Output is correct |
7 |
Incorrect |
37 ms |
17924 KB |
Extra information in the output file |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
17928 KB |
Output is correct |
2 |
Correct |
156 ms |
97396 KB |
Output is correct |
3 |
Correct |
180 ms |
97592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
17928 KB |
Output is correct |
2 |
Correct |
156 ms |
97396 KB |
Output is correct |
3 |
Correct |
180 ms |
97592 KB |
Output is correct |
4 |
Incorrect |
30 ms |
17928 KB |
Extra information in the output file |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
18152 KB |
Output is correct |
2 |
Correct |
193 ms |
113512 KB |
Output is correct |
3 |
Correct |
201 ms |
113380 KB |
Output is correct |
4 |
Correct |
240 ms |
112832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
18152 KB |
Output is correct |
2 |
Correct |
193 ms |
113512 KB |
Output is correct |
3 |
Correct |
201 ms |
113380 KB |
Output is correct |
4 |
Correct |
240 ms |
112832 KB |
Output is correct |
5 |
Incorrect |
29 ms |
18188 KB |
Extra information in the output file |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
18152 KB |
Output is correct |
2 |
Correct |
171 ms |
98576 KB |
Output is correct |
3 |
Correct |
169 ms |
98560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
18152 KB |
Output is correct |
2 |
Correct |
171 ms |
98576 KB |
Output is correct |
3 |
Correct |
169 ms |
98560 KB |
Output is correct |
4 |
Incorrect |
34 ms |
17920 KB |
Extra information in the output file |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
17920 KB |
Output is correct |
2 |
Correct |
171 ms |
113432 KB |
Output is correct |
3 |
Correct |
204 ms |
113648 KB |
Output is correct |
4 |
Correct |
223 ms |
112704 KB |
Output is correct |
5 |
Correct |
32 ms |
18200 KB |
Output is correct |
6 |
Correct |
188 ms |
98416 KB |
Output is correct |
7 |
Correct |
162 ms |
98324 KB |
Output is correct |
8 |
Correct |
231 ms |
99332 KB |
Output is correct |
9 |
Correct |
213 ms |
99432 KB |
Output is correct |
10 |
Correct |
233 ms |
105984 KB |
Output is correct |
11 |
Correct |
263 ms |
104980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
17920 KB |
Output is correct |
2 |
Correct |
171 ms |
113432 KB |
Output is correct |
3 |
Correct |
204 ms |
113648 KB |
Output is correct |
4 |
Correct |
223 ms |
112704 KB |
Output is correct |
5 |
Correct |
32 ms |
18200 KB |
Output is correct |
6 |
Correct |
188 ms |
98416 KB |
Output is correct |
7 |
Correct |
162 ms |
98324 KB |
Output is correct |
8 |
Correct |
231 ms |
99332 KB |
Output is correct |
9 |
Correct |
213 ms |
99432 KB |
Output is correct |
10 |
Correct |
233 ms |
105984 KB |
Output is correct |
11 |
Correct |
263 ms |
104980 KB |
Output is correct |
12 |
Incorrect |
27 ms |
18188 KB |
Extra information in the output file |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
18100 KB |
Output is correct |
2 |
Correct |
44 ms |
20992 KB |
Output is correct |
3 |
Correct |
41 ms |
21048 KB |
Output is correct |
4 |
Correct |
51 ms |
21004 KB |
Output is correct |
5 |
Correct |
60 ms |
21500 KB |
Output is correct |
6 |
Correct |
41 ms |
20924 KB |
Output is correct |
7 |
Correct |
32 ms |
17924 KB |
Output is correct |
8 |
Correct |
166 ms |
97340 KB |
Output is correct |
9 |
Correct |
164 ms |
97392 KB |
Output is correct |
10 |
Correct |
28 ms |
18068 KB |
Output is correct |
11 |
Correct |
181 ms |
113472 KB |
Output is correct |
12 |
Correct |
163 ms |
113548 KB |
Output is correct |
13 |
Correct |
222 ms |
112792 KB |
Output is correct |
14 |
Correct |
32 ms |
18140 KB |
Output is correct |
15 |
Correct |
171 ms |
98356 KB |
Output is correct |
16 |
Correct |
156 ms |
98828 KB |
Output is correct |
17 |
Correct |
220 ms |
99328 KB |
Output is correct |
18 |
Correct |
208 ms |
99228 KB |
Output is correct |
19 |
Correct |
202 ms |
105960 KB |
Output is correct |
20 |
Correct |
318 ms |
104844 KB |
Output is correct |
21 |
Correct |
176 ms |
97636 KB |
Output is correct |
22 |
Correct |
162 ms |
97792 KB |
Output is correct |
23 |
Correct |
171 ms |
98304 KB |
Output is correct |
24 |
Correct |
173 ms |
98308 KB |
Output is correct |
25 |
Correct |
228 ms |
102040 KB |
Output is correct |
26 |
Correct |
167 ms |
98356 KB |
Output is correct |
27 |
Correct |
136 ms |
98300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
18100 KB |
Output is correct |
2 |
Correct |
44 ms |
20992 KB |
Output is correct |
3 |
Correct |
41 ms |
21048 KB |
Output is correct |
4 |
Correct |
51 ms |
21004 KB |
Output is correct |
5 |
Correct |
60 ms |
21500 KB |
Output is correct |
6 |
Correct |
41 ms |
20924 KB |
Output is correct |
7 |
Correct |
32 ms |
17924 KB |
Output is correct |
8 |
Correct |
166 ms |
97340 KB |
Output is correct |
9 |
Correct |
164 ms |
97392 KB |
Output is correct |
10 |
Correct |
28 ms |
18068 KB |
Output is correct |
11 |
Correct |
181 ms |
113472 KB |
Output is correct |
12 |
Correct |
163 ms |
113548 KB |
Output is correct |
13 |
Correct |
222 ms |
112792 KB |
Output is correct |
14 |
Correct |
32 ms |
18140 KB |
Output is correct |
15 |
Correct |
171 ms |
98356 KB |
Output is correct |
16 |
Correct |
156 ms |
98828 KB |
Output is correct |
17 |
Correct |
220 ms |
99328 KB |
Output is correct |
18 |
Correct |
208 ms |
99228 KB |
Output is correct |
19 |
Correct |
202 ms |
105960 KB |
Output is correct |
20 |
Correct |
318 ms |
104844 KB |
Output is correct |
21 |
Correct |
176 ms |
97636 KB |
Output is correct |
22 |
Correct |
162 ms |
97792 KB |
Output is correct |
23 |
Correct |
171 ms |
98304 KB |
Output is correct |
24 |
Correct |
173 ms |
98308 KB |
Output is correct |
25 |
Correct |
228 ms |
102040 KB |
Output is correct |
26 |
Correct |
167 ms |
98356 KB |
Output is correct |
27 |
Correct |
136 ms |
98300 KB |
Output is correct |
28 |
Incorrect |
32 ms |
18176 KB |
Extra information in the output file |
29 |
Halted |
0 ms |
0 KB |
- |