#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=12e4+7, INF=1e9+7;
vector<pair<int,int>>V[LIM];
vector<int>S;
int typ[LIM], A[LIM], B[LIM], czas[LIM], usun[LIM], ile[LIM], ans[LIM];
int rosnie[LIM], maleje[LIM], najw[LIM], najm[LIM], oc[LIM], ktory[LIM];
int cent(int x, int o, int n) {
S.pb(x);
ile[x]=1;
int p=-1, ma=0;
for(auto i : V[x]) if(!usun[i.nd] && i.nd!=o) {
int t=cent(i.nd, x, n);
if(t!=-1) p=t;
ile[x]+=ile[i.nd];
ma=max(ma, ile[i.nd]);
}
ma=max(ma, n-ile[x]);
if(ma<=n/2) p=x;
return p;
}
void DFS(int x, int o, int lst) {
for(auto i : V[x]) if(!usun[i.nd] && i.nd!=o) {
oc[i.nd]=oc[x];
rosnie[i.nd]=rosnie[x];
maleje[i.nd]=maleje[x];
najw[i.nd]=najw[x];
najm[i.nd]=najm[x];
if(lst && i.st<lst) rosnie[i.nd]=0;
if(lst && i.st>lst) maleje[i.nd]=0;
if(lst) {
najw[i.nd]=max(najw[i.nd], i.st);
najm[i.nd]=min(najm[i.nd], i.st);
}
DFS(i.nd, x, i.st);
}
}
void cd(int x, int n, vector<int>pyt) {
S.clear();
x=cent(x, x, n);
cent(x, x, n);
usun[x]=rosnie[x]=maleje[x]=1;
najm[x]=INF;
najw[x]=-INF;
rep(i, V[x].size()) if(!usun[V[x][i].nd]) {
ktory[V[x][i].nd]=i;
oc[V[x][i].nd]=V[x][i].nd;
rosnie[V[x][i].nd]=maleje[V[x][i].nd]=1;
najw[V[x][i].nd]=najm[V[x][i].nd]=V[x][i].st;
DFS(V[x][i].nd, x, V[x][i].st);
}
vector<int>P[V[x].size()], Q, C;
for(auto i : pyt) {
if(typ[i]) {
C.pb(i);
if(A[i]!=x) P[ktory[oc[A[i]]]].pb(i);
} else {
if(oc[A[i]]==oc[B[i]] && A[i]!=x) P[ktory[oc[A[i]]]].pb(i);
else Q.pb(i);
}
}
for(auto i : Q) {
if(A[i]==x && maleje[B[i]] && najw[B[i]]<=czas[i]) ans[i]=1;
if(B[i]==x && rosnie[A[i]] && najw[A[i]]<=czas[i]) ans[i]=1;
if(rosnie[A[i]] && maleje[B[i]] && najm[A[i]]>najw[B[i]])
if(max(najw[A[i]], najw[B[i]])<=czas[i]) ans[i]=1;
}
rep(i, V[x].size()) if(!usun[V[x][i].nd]) cd(V[x][i].nd, ile[V[x][i].nd], P[i]);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k, ilen=0, ilek=0;
cin >> n >> k;
rep(i, n+k-1) {
char c;
cin >> c;
if(c=='S') {
++ilen;
int a, b;
cin >> a >> b; --a; --b;
V[a].pb({ilen, b});
V[b].pb({ilen, a});
} else if(c=='Q') {
cin >> A[ilek] >> B[ilek];
--A[ilek]; --B[ilek]; czas[ilek]=ilen;
++ilek;
} else {
cin >> A[ilek]; --A[ilek];
czas[ilek]=ilen; typ[ilek]=1;
++ilek;
}
}
rep(i, n) sort(all(V[i]));
vector<int>T;
rep(i, k) T.pb(i);
cd(0, n, T);
rep(i, k) if(typ[i]) cout << ans[i] << '\n'; else cout << (ans[i]?"yes":"no") << '\n';
}
Compilation message
servers.cpp: In function 'void cd(int, int, std::vector<int>)':
servers.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
servers.cpp:52:2: note: in expansion of macro 'rep'
52 | rep(i, V[x].size()) if(!usun[V[x][i].nd]) {
| ^~~
servers.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
servers.cpp:75:2: note: in expansion of macro 'rep'
75 | rep(i, V[x].size()) if(!usun[V[x][i].nd]) cd(V[x][i].nd, ile[V[x][i].nd], P[i]);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
100 ms |
20852 KB |
Output is correct |
| 3 |
Correct |
86 ms |
21988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
100 ms |
20852 KB |
Output is correct |
| 3 |
Correct |
86 ms |
21988 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
6872 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
6804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
6804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
