#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e9+10;
const int maxn = 2e5+10;
int n, k, h[maxn];
int pp[maxn][25], pmn[maxn][25], pmx[maxn][25], pin[maxn][25], pde[maxn][25];
vector<pair<int,int>> g[maxn];
void dfs(int u, int ant) {
for(int i = 1; i <= 20; i++) {
if(pp[u][i-1] == -1) {
pp[u][i] = -1;
pmn[u][i] = pmn[u][i-1];
pmx[u][i] = pmx[u][i-1];
pin[u][i] = pin[u][i-1];
}
else {
pp[u][i] = pp[pp[u][i-1]][i-1];
pmn[u][i] = min(pmn[u][i-1],pmn[pp[u][i-1]][i-1]);
pmx[u][i] = max(pmx[u][i-1],pmx[pp[u][i-1]][i-1]);
pin[u][i] = pin[u][i-1]&pin[pp[u][i-1]][i-1]&(pmx[u][i-1] < pmn[pp[u][i-1]][i-1]);
}
}
for(auto V : g[u]) if(V.fr != ant) {
int v = V.fr;
int w = V.sc;
pmn[v][0] = w;
pmx[v][0] = w;
pin[v][0] = 1;
pde[v][0] = 1;
pp[v][0] = u;
h[v] = h[u]+1;
dfs(v,u);
}
}
int lca(int u, int v) {
if(h[v] > h[u]) {
swap(u,v);
}
for(int i = 20; i >= 0; i--) {
if(pp[u][i] != -1 && h[pp[u][i]] >= h[v]) u = pp[u][i];
}
if(u == v) return u;
for(int i = 20; i >= 0; i--) {
if(pp[u][i] != -1 && pp[v][i] != -1 && pp[u][i] != pp[v][i]) {
u = pp[u][i];
v = pp[v][i];
}
}
return pp[u][0];
}
int32_t main() {
freopen("in.in", "r", stdin);
cin >> n >> k;
vector<pair<pair<int,int>,pair<int,int>>> qrys;
for(int i = 1; i <= n+k-1; i++) {
char op; cin >> op;
if(op == 'S') {
int u,v;cin >> u >> v;
g[u].pb(mp(v,i));
g[v].pb(mp(u,i));
}
else if(op == 'Q') {
int u,v; cin >> u >> v;
qrys.pb(mp(mp(0,i),mp(u,v)));
}
}
pp[1][0] = -1;
pmn[1][0] = inf;
pmx[1][0] = -inf;
pin[1][0] = 1;
pde[1][0] = 1;
dfs(1,1);
for(auto X : qrys) {
int w = X.fr.sc;
int u = X.sc.sc;
int v = X.sc.fr;
int lc = lca(u,v);
string ans = "yes";
vector<int> ordu, ordv, ords;
// while(u != lc) {
// ordu.pb(pmn[u][0]);
// u = pp[u][0];
// }
for(int i = 20; i >= 0; i--) {
if(pp[u][i] != -1 && h[pp[u][i]] >= h[lc]) {
if(pin[u][i] == 0) ans = "no";
ordu.pb(pmn[u][i]);
ordu.pb(pmx[u][i]);
u = pp[u][i];
}
}
while(v != lc) {
ordv.pb(pmn[v][0]);
v = pp[v][0];
}
for(auto x : ordu) ords.pb(x);
reverse(all(ordv));
for(auto x : ordv) ords.pb(x);
for(int i = 0; i < ords.size(); i++) {
if(ords[i] > w) ans = "no";
if(i != 0 && ords[i] < ords[i-1]) ans = "no";
}
cout << ans << endl;
}
}
Compilation message
servers.cpp: In function 'int32_t main()':
servers.cpp:124:26: 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]
124 | for(int i = 0; i < ords.size(); i++) {
| ~~^~~~~~~~~~~~~
servers.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | freopen("in.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
