#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma region dalykai
template <typename F>
void _debug(F f)
{
f();
}
#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion
struct event_t
{
char type; // s, q, c (kol kas nemoku c)
int a, b;
};
void dfs(int v, int p, int val, vp32 &dp, vvp32 &adj)
{
for (auto &[next, index] : adj[v])
{
if (next == p)
{
continue;
}
dp[next].first = (val > index) ? dp[v].first + 1 : 1;
dp[next].second = (val < index) ? dp[v].second + 1 : 1;
dfs(next, v, index, dp, adj);
}
}
void find_lift(int v, int p, vi32 &depth, vvp32 &anc, vvp32 &adj)
{
for (auto &[next, index] : adj[v])
{
if (next == p)
{
continue;
}
depth[next] = depth[v] + 1;
anc[next][0] = {v, index};
find_lift(next, v, depth, anc, adj);
}
}
p32 find_ancestor(int v, int k, vvp32 &anc)
{
if (!k)
{
return {v, -1};
}
p32 ans = {v, 0};
for (int bit = 31 - __builtin_clz(k); bit >= 0; bit--)
{
if (!(k & (1 << bit)))
{
continue;
}
if (anc[ans.first][bit].first == -1)
{
return {-1, -1};
}
ans = anc[ans.first][bit];
}
return ans;
}
int find_lca(int a, int b, vi32 &depth, vvp32 &anc)
{
int val_a = 0, val_b = 0;
if (depth[a] > depth[b])
{
tie(a, val_a) = find_ancestor(a, depth[a] - depth[b], anc);
}
else
{
tie(b, val_b) = find_ancestor(b, depth[b] - depth[a], anc);
}
if (a == -1)
{
return -1;
}
if (a == b)
{
return a;
}
for (int bit = (int)anc[0].size() - 1; bit >= 0; bit--)
{
if (anc[a][bit] != anc[b][bit])
{
tie(a, val_a) = anc[a][bit];
tie(b, val_b) = anc[b][bit];
}
}
if (val_a > val_b)
{
return -1;
}
return anc[a][0].first;
}
int main()
{
#ifndef _AAAAAAAAA
ios_base::sync_with_stdio(false);
cin.tie(0);
#else
freopen("servers.in", "r", stdin);
#ifndef __linux__
atexit([]()
{
freopen("con", "r", stdin);
system("pause"); });
#endif
#endif
int n, query;
cin >> n >> query;
vector<event_t> event(n - 1 + query);
vvp32 adj(n);
for (int i = 0; auto &[type, a, b] : event)
{
cin >> type >> a;
if (type != 'C')
{
cin >> b;
}
a--;
b--;
if (type == 'S')
{
adj[a].emplace_back(b, i);
adj[b].emplace_back(a, i);
}
i++;
}
vp32 dp(n);
dfs(0, -1, INT_MAX, dp, adj);
vi32 depth(n);
vvp32 anc(n, vp32(31 - __builtin_clz(n), {-1, -1}));
find_lift(0, -1, depth, anc, adj);
anc[0][0] = {-1, INT_MAX};
for (int level = 1; level < (int)anc[0].size(); level++)
{
for (int i = 0; i < n; i++)
{
int a = anc[i][level - 1].first;
if (a == -1)
{
continue;
}
anc[i][level] = anc[a][level - 1];
}
}
for (int i = 0; auto &[type, a, b] : event)
{
if (type == 'S')
{
i++;
continue;
}
if (type == 'C')
{
cout << "0\n";
i++;
continue;
}
if (a == b)
{
cout << "yes\n";
i++;
continue;
}
// dabar a - duomenu id, b - virsune
swap(a, b);
int lca = find_lca(a, b, depth, anc);
if (lca == -1 || anc[b][0].second > i)
{
cout << "no\n";
i++;
continue;
}
if (depth[b] - depth[lca] > dp[b].second || depth[a] - depth[lca] > dp[a].first)
{
cout << "no\n";
i++;
continue;
}
cout << "yes\n";
i++;
}
return 0;
}
Compilation message
servers.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
8 | #pragma region dalykai
|
servers.cpp:43: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
43 | #pragma endregion
|
servers.cpp: In function 'int main()':
servers.cpp:168:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
168 | for (int i = 0; auto &[type, a, b] : event)
| ^~~~
servers.cpp:209:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
209 | for (int i = 0; auto &[type, a, b] : event)
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
1992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
1992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
3264 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
3264 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
2004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
2004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
3280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
3280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
2004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
2004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
