#include <bits/stdc++.h>
using namespace std;
const int N=240000+7;
const int K = 20;
int n;
int k;
vector<pair<int, int>> gg[N];
vector<pair<int,int>> q2[N];
int q1[N];
int p[N];
int pskip[K][N];
int dep[N];
int euler_tour[2 * N];
int tour_sz;
int first_time_on_tour[N];
int last_time_on_tour[N];
int lg2[2 * N];
int idup[N];
//vector<int> g[N];
pair<int, int> tab_lca[2 * N][K];
vector<int> who_have_id[N];
int who_has_id[N];
void dfs_lca(int a, int par = 0)
{
p[a] = par;
euler_tour[++tour_sz] = a;
first_time_on_tour[a] = last_time_on_tour[a] = tour_sz;
vector<pair<int, int>> ngg;
for (auto &it : gg[a])
{
int b=it.first;
int i=it.second;
if (b==par){
continue;
}
ngg.push_back(it);
who_has_id[i]=b;
idup[b]=i;
dep[b] = 1 + dep[a];
dfs_lca(b, a);
euler_tour[++tour_sz] = a;
last_time_on_tour[a] = tour_sz;
}
gg[a]=ngg;
}
void lcaTM()
{
dfs_lca(1);
for (int i = 2; i <= tour_sz; i++)
{
lg2[i] = 1 + lg2[i / 2];
}
for (int i = 1; i <= tour_sz; i++)
{
tab_lca[i][0] = {dep[euler_tour[i]], euler_tour[i]};
}
for (int k = 1; (1 << k) <= tour_sz; k++)
{
for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++)
{
tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]);
}
}
}
int lca(int a, int b)
{
if (first_time_on_tour[a] > last_time_on_tour[b])
{
swap(a, b);
}
a = first_time_on_tour[a];
b = last_time_on_tour[b];
int k = lg2[b - a + 1];
return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second;
}
int goup(int a,int cnt){
assert(cnt>=0);
for(int i=0;i<K;i++){
if(cnt&(1<<i)){
a=pskip[i][a];
}
}
return a;
}
int sol[N];
int tp[N];
int inc[N];
int dcr[N];
int cnt[N];
void dfs2(int a){
inc[a]=max(inc[a],1);
dcr[a]=max(dcr[a],1);
for (auto &it:gg[a]){
int b=it.first;
if(b==p[a]){
continue;
}
if(idup[a]<idup[b]){
inc[b]=1+inc[a];
}else{
dcr[b]=1+dcr[a];
}
dfs2(b);
}
///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n";
}
bool home=0;
int main() {
if(0){
freopen("them.txt","r",stdin);
freopen("output2.txt","w",stdout);
/*char s[1000];
while(cin.getline(s,1000)){
if(s[0]!='Q'){
cout<<s<<"\n";
}
}*/
string s;
while(cin>>s){
if(s=="yes"||s=="no"){
continue;
}
cout<<s<<"\n";
}
exit(0);
}
if(0) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
else {
home=1;
freopen("___input___.txt","r",stdin);
/// freopen("them.txt","r",stdin);
if(0)freopen("out.txt","w",stdout);
}
cin>>n>>k;
int cnt3=0;
for(int i=1;i<=n+k-1;i++){
string s;
cin>>s;
assert(s=="S"||s=="Q"||s=="C");
if(s=="S"){
tp[i]=2;
int a,b;
cin>>a>>b;
///g[a].push_back(b);
///g[b].push_back(a);
gg[a].push_back({b, i});
gg[b].push_back({a, i});
sol[i]=-1;
}
if(s=="Q"){
int a,b;
cin>>a>>b;
if(a==b){
tp[i]=1;
sol[i]=1;
}else{
q2[a].push_back({b, i});
tp[i]=1;
sol[i]=-2;
}
}
if(s=="C"){
cnt3++;
int a;
cin>>a;
/// cout<<i<<" = "<<a<<"\n";
q1[i]=a;
sol[i]=-3;
tp[i]=3;
}
}
lcaTM();
dfs2(1);
/// solve q1 for the general case
for (int i=1;i<=n;i++){
pskip[0][i]=p[i];
}
for (int k=1;k<K;k++){
for (int i=1;i<=n;i++){
pskip[k][i]=pskip[k-1][pskip[k-1][i]];
}
}
for (int a=1;a<=n;a++){
for (auto &it:q2[a]){
int b=it.first,i=it.second;
/**
**/
/// drumul de la b la a e crescator?
vector<int> guys_x,guys_y;
int x=a,y=b,z;
swap(x,y);
z=lca(x,y);
int last=-1;
if(y!=z){
last=idup[y];
}else{
last=idup[goup(x,dep[x]-dep[z]-1)];
}
bool ok=1;
ok&=(inc[y]>=dep[y]-dep[z]);
ok&=(dcr[x]>=dep[x]-dep[z]);
if(x!=z&&y!=z){
ok&=(idup[goup(x,dep[x]-dep[z]-1)]<=idup[goup(y,dep[y]-dep[z]-1)]);
}
ok&=(last<i);
sol[i]=ok;
}
}
const int INF=(int)1e9+7;
int cnt_2=0;
int ciq=0;
for (int i=1;i<=n+k-1&&cnt3!=0;i++){
if(tp[i]==2){
cnt_2++;
int cnt_down=max(1,inc[who_has_id[i]]-1);
int vertex=who_has_id[i];
for (int j=1;j<=cnt_down;j++){
cnt[vertex]++;
vertex=p[vertex];
}
}
if (q1[i]){
ciq++;
assert(tp[i]==3);
int vertex=q1[i];
int ret=1;
for (auto &it : gg[vertex]){
int v2=it.first;
ret+=cnt[v2];
}
int cnt_down=min(dcr[q1[i]],dep[q1[i]]);
int down=0;
for (int j=1;j<=cnt_down;j++){
ret+=(idup[vertex]<i);
for (auto &it:gg[p[vertex]]){
int v2=it.first;
if(idup[vertex]<idup[v2]){
ret+=cnt[v2];
}
}
vertex=p[vertex];
}
sol[i]=ret;
}
}
if(cnt3){
assert(cnt_2==n-1);
}
unsigned long long h=0;
for(int i=1;i<=n+k-1;i++)h=7777*h+sol[i];
if(home){
assert(h==8758581888253777949);
cout<<"good\n";
exit(0);
}
for (int i=1;i<=n+k-1;i++){
if(tp[i]==1){
assert(sol[i]==0||sol[i]==1);
///continue;
if(sol[i]==1){
cout<<"yes\n";
}else{
cout<<"no\n";
}
}
if (tp[i]==3){
cout<<sol[i]<<"\n";
}
}
return 0;
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:256:29: warning: unused variable 'down' [-Wunused-variable]
256 | int down=0;
| ^~~~
servers.cpp:229:19: warning: unused variable 'INF' [-Wunused-variable]
229 | const int INF=(int)1e9+7;
| ^~~
servers.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | freopen("them.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:122:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | freopen("output2.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:142:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | freopen("___input___.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:144:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | if(0)freopen("out.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
34772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
34772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
34824 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
34824 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
34816 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
34816 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
34772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
34772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
34776 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
34776 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
34772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
34772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
