#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 2e5 + 10;
int n, m, id = 0;
vector < int > flatten, depth, st;
vector < array < int , 3 >> queries;
vector < vector < int >> mx_inc, mx_dec, nxt;
vector < vector < pair < int , int >>> adj, increase, decrease;
void dfs(int node, int par, int last) {
increase[0][node] = decrease[0][node] = {par, last};
depth[node] = depth[par] + 1;
st[node] = flatten.size();
flatten.push_back(node);
for(auto child : adj[node]) {
if(child.first == par) continue;
dfs(child.first, node, child.second);
flatten.push_back(node);
}
}
void build() {
nxt[0] = flatten;
for(int i = 1 ; (1ll << i) <= flatten.size() ; i++) {
for(int j = 0 ; j + (1ll << i) <= flatten.size() ; j++) {
int a = nxt[i - 1][j], b = nxt[i - 1][j + (1ll << (i - 1))];
if(depth[a] < depth[b]) {
nxt[i][j] = a;
} else {
nxt[i][j] = b;
}
}
}
}
int LCA(int l, int r) {
l = st[l], r = st[r];
if (l > r) swap(l, r);
int pw = __lg(r - l + 1);
int a = nxt[pw][l], b = nxt[pw][r - (1 << pw) + 1];
if(depth[a] < depth[b]) {
return a;
} else {
return b;
}
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
cin >> n >> m;
depth = st = vector < int > (n + 2);
adj = vector < vector < pair < int , int >>> (n + 1);
nxt = vector < vector < int >> (22, vector < int > (n * 2 + 5));
mx_dec = vector < vector < int >> (22, vector < int > (n + 2, 1e9));
mx_inc = vector < vector < int >> (22, vector < int > (n + 2, -1e9));
increase = decrease = vector < vector < pair < int , int >>> (22, vector < pair < int , int >> (n + 1));
for(int i = 0 ; i < m + n - 1 ; i++) {
int a, b; string ty;
cin >> ty >> a >> b;
if(ty == "S") {
adj[a].push_back({b, i + 1});
adj[b].push_back({a, i + 1});
} else if(ty == "Q") {
queries.push_back({a, b, i + 1});
}
}
dfs(1, 0, 0), build();
for(int i = 1 ; i <= n ; i++) {
mx_dec[0][i] = decrease[0][i].second;
// cout << "(" << increase[0][i].first << ", " << increase[0][i].second << "), (" << decrease[0][i].first << ", " << decrease[0][i].second << ")" << endl;
}
// cout << endl;
for(int i = 1 ; i <= 20 ; i++) {
for(int j = 1 ; j <= n ; j++) {
auto a = increase[i - 1][j];
if(a.first != -1) {
auto b = increase[i - 1][a.first];
if(a.second <= b.second) {
increase[i][j] = b;
} else {
increase[i][j] = {-1, -1};
}
}
a = decrease[i - 1][j];
if(a.first != -1) {
auto b = decrease[i - 1][a.first];
if(a.second >= b.second) {
decrease[i][j] = b;
mx_dec[i][j] = a.second;
} else {
decrease[i][j] = {-1, -1};
}
}
// cerr << "(" << increase[i][j].first << ", " << increase[i][j].second << "), (" << decrease[i][j].first << ", " << decrease[i][j].second << ")" << endl;
}
}
for(auto i : queries) {
int l = i[0], r = i[1], t = i[2];
int lc = LCA(l, r);
int d1 = dist(l, LCA(l, r));
int d2 = dist(r, LCA(l, r));
int val1 = 0;
bool check1 = 1;
for(int i = 20 ; i >= 0 ; i--) {
if(d1 & (1ll << i)) {
if(decrease[i][l].first < 0) {
check1 = 0;
break;
} else if(mx_dec[i][l] > t) {
check1 = 0;
break;
} else {
val1 = decrease[i][l].second;
l = decrease[i][l].first;
}
}
}
int val2 = 0;
bool check2 = 1;
for(int i = 20 ; i >= 0 ; i--) {
if(d2 & (1ll << i)) {
if(increase[i][r].first < 0) {
check2 = 0;
break;
} else if(increase[i][r].second > t) {
check1 = 0;
break;
} else {
val2 = increase[i][r].second;
r = increase[i][r].first;
}
}
}
cout << (check1 && check2 && val1 >= val2? "yes" : "no") << endl;
}
return 0 ;
}
Compilation message
servers.cpp: In function 'void build()':
servers.cpp:30:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 1 ; (1ll << i) <= flatten.size() ; i++) {
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:31:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int j = 0 ; j + (1ll << i) <= flatten.size() ; j++) {
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:118:13: warning: unused variable 'lc' [-Wunused-variable]
118 | int lc = LCA(l, r);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
3652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
3652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
3780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
3780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
4052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
4052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
4816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
4816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
4560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
4560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
