#include <bits/stdc++.h>
const int MAXN = 120010 ;
const int LOG = 20 ;
using namespace std ;
int N , K ;
int aresta_pai[MAXN] , max_crescente[MAXN] , max_decrescente[MAXN] ;
int last_crescente[MAXN] , last_decrescente[MAXN] ;
int lvl[MAXN] , tin[MAXN] , tout[MAXN] ;
int tab[LOG][MAXN] ;
pair<int,int> queries[MAXN] ;
vector< pair<int,int> > adj[MAXN] ;
int dsu[MAXN] ;
int find(int x) { return dsu[x] = (dsu[x] == x ) ? x : find(dsu[x]) ; }
bool join(int x, int y, bool consulta = false )
{
x = find(x) ;
y = find(y) ;
if(x == y) return false ;
if( rand() % 2 ) swap(x,y) ;
if( !consulta ) dsu[x] = y ;
return true ;
}
int currTime ;
void dfs(int x)
{
tin[x] = tout[x] = ++currTime ;
for(int i = 1 ; i< LOG && tab[i-1][x] ; i++ )
tab[i][x] = tab[i-1][ tab[i-1][x] ] ;
max_crescente[x] = max_decrescente[x] = tab[0][x] ;
if( tab[0][ tab[0][x] ] && aresta_pai[x] < aresta_pai[tab[0][x]] )
max_crescente[x] = max_crescente[ tab[0][x] ] ;
if( tab[0][ tab[0][x] ] && aresta_pai[x] > aresta_pai[tab[0][x]] )
max_decrescente[x] = max_decrescente[ tab[0][x] ] ;
for(auto e : adj[x] )
{
if(e.first == tab[0][x]) continue ;
tab[0][e.first] = x ;
aresta_pai[e.first] = e.second ;
lvl[e.first] = lvl[x]+1 ;
dfs(e.first) ;
}
tout[x] = currTime ;
}
int lca(int x, int y)
{
if( lvl[x] < lvl[y] ) swap(x,y) ;
for(int i = LOG-1 ; i >= 0 ; i-- )
if( tab[i][x] && lvl[tab[i][x]] >= lvl[y] )
x = tab[i][x] ;
if(x==y)return y ;
for(int i = LOG-1 ; i >= 0 ; i-- )
if( tab[i][x] && tab[i][x] != tab[i][y] )
{
x = tab[i][x] ;
y= tab[i][y] ;
}
return tab[0][x] ;
}
int main()
{
scanf("%d %d", &N, &K ) ;
for(int i = 1 , a ,b ; i < N+K ; i++ )
{
char c ;
scanf(" %c %d", &c , &queries[i].first ) ;
if(c == 'C') continue ;
else scanf("%d", &queries[i].second ) ;
if( c == 'S' )
{
a = queries[i].first ;
b = queries[i].second ;
queries[i] = make_pair(-a,-b) ;
adj[a].push_back( make_pair(b,i) ) ;
adj[b].push_back( make_pair(a,i) ) ;
}
}
dfs(1) ;
iota(dsu+1, dsu+1+N , 1 ) ;
for(int i = 1 ; i < N+K ; i++ )
{
if(queries[i].second == 0) continue ;
if( queries[i].first < 0 )
{
join(-queries[i].first, -queries[i].second ) ;
continue ;
}
if( join(queries[i].first, queries[i].second, true) ) { printf("no\n") ; continue ; }
int k = lca(queries[i].first, queries[i].second) ;
if( lvl[ max_decrescente[queries[i].first] ] <= lvl[k] && lvl[ max_crescente[queries[i].second] ] <= lvl[k] )
{
if( k == queries[i].second || k == queries[i].first ) { printf("yes\n") ; continue ; }
int x = queries[i].first ;
int y = queries[i].second ;
for(int g = LOG-1 ; g >= 0 ; g-- )
if( tab[g][x] && lvl[ tab[g][x] ] > lvl[k] )
x = tab[g][x] ;
for(int g = LOG-1 ; g >= 0 ; g-- )
if( tab[g][y] && lvl[ tab[g][y] ] > lvl[k] )
y = tab[g][y] ;
if( aresta_pai[y] < aresta_pai[x] ) { printf("yes\n" ) ; continue ; }
}
printf("no\n") ;
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d %d", &N, &K ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
servers.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf(" %c %d", &c , &queries[i].first ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:93:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | else scanf("%d", &queries[i].second ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
4420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
4420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
4556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
4556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
4544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
4544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
4432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
4496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
4496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
