#include <bits/stdc++.h>
#define ll long long
#define oo 1e9
#define pii pair<int, int>
using namespace std;
const int MAX = 12e4 + 4, LOGMAX = 18;
int n, m;
int par[LOGMAX][MAX];
int tin[MAX], tout[MAX];
int h[MAX];
vector<pii> g[MAX];
int dp[MAX][2];
int parl[MAX];
int t = 1;
void dfs(int node, int p){
par[0][node] = p;
tin[node] = t++;
for(pii to : g[node]){
if(p == to.first) continue;
h[to.first] = h[node] + 1;
dp[to.first][0] = node;
dp[to.first][1] = node;
if((parl[node] > to.second) || !parl[node]){
dp[to.first][0] = dp[node][0];
}
if((parl[node] < to.second) || !parl[node]){
dp[to.first][1] = dp[node][1];
}
parl[to.first] = to.second;
dfs(to.first, node);
}
tout[node] = t++;
}
bool isAnc(int u, int v){
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lift(int u, int l){
for(int j = LOGMAX - 1; j >= 0; j--){
if(!isAnc(par[j][u], l)) u = par[j][u];
}
return u;
}
int lca(int u, int v){
if(isAnc(u, v)) return u;
if(isAnc(v, u)) return v;
return par[0][lift(u, v)];
}
int dsu[MAX];
int f(int node){
if(dsu[node] < 0) return node;
return dsu[node] = f(dsu[node]);
}
void unite(int u, int v){
u = f(u), v = f(v);
if(u == v) return;
if(-dsu[u] < -dsu[v]) swap(u, v);
dsu[u] += dsu[v];
dsu[v] = u;
}
vector<array<int, 2>> Q;
vector<bool> ans;
int main(){
memset(dsu, -1, sizeof(dsu));
cin >> n >> m;
for(int i = 1; i <= n + m - 1; i++){
string s; cin >> s;
if(s[0] == 'S'){
int u, v; cin >> u >> v;
g[u].push_back({v, i});
g[v].push_back({u, i});
Q.push_back({-u, -v});
}
else{
int u, a; cin >> u >> a;
Q.push_back({a, u});
}
}
dp[1][0] = 1;
dp[1][1] = 1;
dfs(1, 1);
for(int j = 1; j < LOGMAX; j++){
for(int i = 1; i <= n; i++){
par[j][i] = par[j - 1][par[j - 1][i]];
}
}
for(auto a : Q){
if(a[0] < 0){
unite(-a[0], -a[1]);
continue;
}
if(a[0] == a[1]){
cout << "yes\n";
continue;
}
if(f(a[0]) != f(a[1])){
cout << "no\n";
continue;
}
if(!isAnc(a[0], a[1]) && !isAnc(a[1], a[0]) && parl[lift(a[0], a[1])] > parl[lift(a[1], a[0])]){
cout << "no\n";
continue;
}
int l = lca(a[0], a[1]);
if(h[dp[a[1]][1]] <= h[l] && h[dp[a[0]][0]] <= h[l]) cout << "yes\n";
else cout << "no\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
16328 KB |
Output is correct |
2 |
Correct |
62 ms |
17608 KB |
Output is correct |
3 |
Correct |
90 ms |
18144 KB |
Output is correct |
4 |
Correct |
70 ms |
17812 KB |
Output is correct |
5 |
Correct |
60 ms |
18172 KB |
Output is correct |
6 |
Correct |
87 ms |
17860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
16328 KB |
Output is correct |
2 |
Correct |
62 ms |
17608 KB |
Output is correct |
3 |
Correct |
90 ms |
18144 KB |
Output is correct |
4 |
Correct |
70 ms |
17812 KB |
Output is correct |
5 |
Correct |
60 ms |
18172 KB |
Output is correct |
6 |
Correct |
87 ms |
17860 KB |
Output is correct |
7 |
Incorrect |
9 ms |
16332 KB |
Extra information in the output file |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
16324 KB |
Output is correct |
2 |
Correct |
195 ms |
24628 KB |
Output is correct |
3 |
Correct |
296 ms |
24640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
16324 KB |
Output is correct |
2 |
Correct |
195 ms |
24628 KB |
Output is correct |
3 |
Correct |
296 ms |
24640 KB |
Output is correct |
4 |
Incorrect |
9 ms |
16332 KB |
Extra information in the output file |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
16224 KB |
Output is correct |
2 |
Correct |
153 ms |
33776 KB |
Output is correct |
3 |
Correct |
152 ms |
33632 KB |
Output is correct |
4 |
Correct |
142 ms |
33548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
16224 KB |
Output is correct |
2 |
Correct |
153 ms |
33776 KB |
Output is correct |
3 |
Correct |
152 ms |
33632 KB |
Output is correct |
4 |
Correct |
142 ms |
33548 KB |
Output is correct |
5 |
Incorrect |
9 ms |
16728 KB |
Extra information in the output file |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
16312 KB |
Output is correct |
2 |
Correct |
191 ms |
25224 KB |
Output is correct |
3 |
Correct |
160 ms |
25504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
16312 KB |
Output is correct |
2 |
Correct |
191 ms |
25224 KB |
Output is correct |
3 |
Correct |
160 ms |
25504 KB |
Output is correct |
4 |
Incorrect |
9 ms |
16336 KB |
Extra information in the output file |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
16320 KB |
Output is correct |
2 |
Correct |
174 ms |
33948 KB |
Output is correct |
3 |
Correct |
159 ms |
33584 KB |
Output is correct |
4 |
Correct |
143 ms |
33668 KB |
Output is correct |
5 |
Correct |
63 ms |
17096 KB |
Output is correct |
6 |
Correct |
189 ms |
25072 KB |
Output is correct |
7 |
Correct |
226 ms |
25536 KB |
Output is correct |
8 |
Correct |
305 ms |
26284 KB |
Output is correct |
9 |
Correct |
234 ms |
26088 KB |
Output is correct |
10 |
Correct |
168 ms |
30592 KB |
Output is correct |
11 |
Correct |
292 ms |
29812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
16320 KB |
Output is correct |
2 |
Correct |
174 ms |
33948 KB |
Output is correct |
3 |
Correct |
159 ms |
33584 KB |
Output is correct |
4 |
Correct |
143 ms |
33668 KB |
Output is correct |
5 |
Correct |
63 ms |
17096 KB |
Output is correct |
6 |
Correct |
189 ms |
25072 KB |
Output is correct |
7 |
Correct |
226 ms |
25536 KB |
Output is correct |
8 |
Correct |
305 ms |
26284 KB |
Output is correct |
9 |
Correct |
234 ms |
26088 KB |
Output is correct |
10 |
Correct |
168 ms |
30592 KB |
Output is correct |
11 |
Correct |
292 ms |
29812 KB |
Output is correct |
12 |
Incorrect |
9 ms |
16588 KB |
Extra information in the output file |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
16192 KB |
Output is correct |
2 |
Correct |
67 ms |
17756 KB |
Output is correct |
3 |
Correct |
100 ms |
17920 KB |
Output is correct |
4 |
Correct |
64 ms |
17904 KB |
Output is correct |
5 |
Correct |
61 ms |
18032 KB |
Output is correct |
6 |
Correct |
90 ms |
17676 KB |
Output is correct |
7 |
Correct |
52 ms |
17388 KB |
Output is correct |
8 |
Correct |
214 ms |
24684 KB |
Output is correct |
9 |
Correct |
287 ms |
24772 KB |
Output is correct |
10 |
Correct |
51 ms |
17428 KB |
Output is correct |
11 |
Correct |
159 ms |
33748 KB |
Output is correct |
12 |
Correct |
153 ms |
33672 KB |
Output is correct |
13 |
Correct |
161 ms |
33492 KB |
Output is correct |
14 |
Correct |
48 ms |
17092 KB |
Output is correct |
15 |
Correct |
187 ms |
25092 KB |
Output is correct |
16 |
Correct |
166 ms |
25736 KB |
Output is correct |
17 |
Correct |
217 ms |
26044 KB |
Output is correct |
18 |
Correct |
250 ms |
26044 KB |
Output is correct |
19 |
Correct |
179 ms |
30692 KB |
Output is correct |
20 |
Correct |
210 ms |
29776 KB |
Output is correct |
21 |
Correct |
207 ms |
25280 KB |
Output is correct |
22 |
Correct |
237 ms |
25616 KB |
Output is correct |
23 |
Correct |
207 ms |
25536 KB |
Output is correct |
24 |
Correct |
207 ms |
25532 KB |
Output is correct |
25 |
Correct |
189 ms |
27508 KB |
Output is correct |
26 |
Correct |
153 ms |
25024 KB |
Output is correct |
27 |
Correct |
152 ms |
25052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
16192 KB |
Output is correct |
2 |
Correct |
67 ms |
17756 KB |
Output is correct |
3 |
Correct |
100 ms |
17920 KB |
Output is correct |
4 |
Correct |
64 ms |
17904 KB |
Output is correct |
5 |
Correct |
61 ms |
18032 KB |
Output is correct |
6 |
Correct |
90 ms |
17676 KB |
Output is correct |
7 |
Correct |
52 ms |
17388 KB |
Output is correct |
8 |
Correct |
214 ms |
24684 KB |
Output is correct |
9 |
Correct |
287 ms |
24772 KB |
Output is correct |
10 |
Correct |
51 ms |
17428 KB |
Output is correct |
11 |
Correct |
159 ms |
33748 KB |
Output is correct |
12 |
Correct |
153 ms |
33672 KB |
Output is correct |
13 |
Correct |
161 ms |
33492 KB |
Output is correct |
14 |
Correct |
48 ms |
17092 KB |
Output is correct |
15 |
Correct |
187 ms |
25092 KB |
Output is correct |
16 |
Correct |
166 ms |
25736 KB |
Output is correct |
17 |
Correct |
217 ms |
26044 KB |
Output is correct |
18 |
Correct |
250 ms |
26044 KB |
Output is correct |
19 |
Correct |
179 ms |
30692 KB |
Output is correct |
20 |
Correct |
210 ms |
29776 KB |
Output is correct |
21 |
Correct |
207 ms |
25280 KB |
Output is correct |
22 |
Correct |
237 ms |
25616 KB |
Output is correct |
23 |
Correct |
207 ms |
25536 KB |
Output is correct |
24 |
Correct |
207 ms |
25532 KB |
Output is correct |
25 |
Correct |
189 ms |
27508 KB |
Output is correct |
26 |
Correct |
153 ms |
25024 KB |
Output is correct |
27 |
Correct |
152 ms |
25052 KB |
Output is correct |
28 |
Incorrect |
9 ms |
16336 KB |
Extra information in the output file |
29 |
Halted |
0 ms |
0 KB |
- |