#include <bits/stdc++.h>
#define DIMN 120010
using namespace std;
int elem;
int rmq_lca[20][2*DIMN] , eul[2*DIMN] , first[DIMN] , nv[2*DIMN] , logg[2*DIMN];
int rmqc[20][DIMN] , rmqd[20][DIMN] , rmqt[20][DIMN] , maxi[20][DIMN];
vector <pair <int , int> > v[DIMN];
pair <int , int> tt[DIMN];
struct queryuri{
int x , y , mch;
} qry[DIMN];
void dfs (int nod , int fth , int val , int lvl){
int i , vecin , cost;
eul[++elem] = nod;
first[nod] = elem;
nv[elem] = lvl;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
cost = v[nod][i].second;
if (vecin == fth){
tt[nod] = make_pair(vecin , val);
continue;
}
dfs(vecin , nod , cost , lvl + 1);
eul[++elem] = nod;
nv[elem] = lvl;
}
}
int query (int x, int y){
int px , py , len;
px = first[x];
py = first[y];
if (px > py)
swap(px , py);
len = py - px + 1;
len = logg[len]; /// cea mai mare p2 <= len
if (nv[ rmq_lca[len][px] ] < nv[ rmq_lca[len][py - (1 << len) + 1] ])
return eul[rmq_lca[len][px]];
else return eul[rmq_lca[len][py - (1 << len) + 1]];
}
int qmaxi (int x , int y){
int p2 , val = 0;
for (p2 = 19 ; p2 >= 0 ; p2--){
if (nv[x] - (1 << p2) >= nv[y]){
val = max(val , maxi[p2][x]);
x = rmqt[p2][x];
}
}
return val;
}
int ok (int x , int y , int fth){
int p2 , val = 1 , y2 , x2;
y2 = y;
for (p2 = 19 ; p2 >= 0 ; p2--){
if (nv[y] - (1 << p2) >= nv[fth]){
val = (val & rmqc[p2][y]);
y = rmqt[p2][fth];
}
}
if (!val)
return 0;
val = 1;
x2 = x;
for (p2 = 19 ; p2 >= 0 ; p2--){
if (nv[x] - (1 << p2) >= nv[fth]){
val = (val & rmqd[p2][x]);
x = rmqt[p2][x];
}
}
if (!val)
return 0;
if (x2 == fth || y2 == fth)
return 1;
for (p2 = 19 ; p2 >= 0 ; p2--){
if (nv[x2] - (1 << p2) > nv[fth])
x2 = rmqt[p2][x2];
if (nv[y2] - (1 << p2) > nv[fth])
y2 = rmqt[p2][y2];
}
return tt[y2].second < tt[x2].second;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , q , cnt , i , x , y , mch = 0 , powe , fth , j , vecin;
char c;
fscanf (fin,"%d%d\n",&n,&q);
cnt = 0;
for (i = 1 ; i <= n + q - 1 ; i++){
c = fgetc(fin);
if ( c == 'S' ){
fscanf (fin,"%d%d\n",&x,&y);
mch++;
v[x].push_back(make_pair(y , mch));
v[y].push_back(make_pair(x , mch));
}
else if ( c == 'Q' ){
fscanf (fin,"%d%d\n",&x,&y);
qry[++cnt] = {x , y , mch};
}
else { /// momentan nimic
}
}
/// vrei sa ai lca disponibil
dfs (1 , 0 , 0 , 1);
for (i = 2 ; i <= 2 * n ; i++)
logg[i] = 1 + logg[i / 2];
for (i = 1 ; i <= elem ; i++)
rmq_lca[0][i] = i;
for (powe = 1 ; (1 << powe) <= elem ; powe++){
for (i = 1 ; i + (1 << powe) - 1 <= elem ; i++){
if (nv[ rmq_lca[powe-1][i] ] < nv[ rmq_lca[powe-1][i + (1 << (powe - 1) )] ])
rmq_lca[powe][i] = rmq_lca[powe-1][i];
else rmq_lca[powe][i] = rmq_lca[powe-1][i + (1 << (powe - 1) )];
}
}
for (i = 1 ; i <= n ; i++){
rmqt[0][i] = tt[i].first;
}
for (powe = 1 ; (1 << powe) <= n ; powe++){
for (i = 1 ; i <= n ; i++){
rmqt[powe][i] = rmqt[powe - 1][rmqt[powe - 1][i]];
}
}
/// imi va mai trb un rmqc si rmqd
for (i = 1 ; i <= n ; i++){
rmqc[0][i] = rmqd[0][i] = 1;
maxi[0][i] = tt[i].second;
}
for (powe = 1 ; (1 << powe) <= n ; powe++){
for (i = 1 ; i <= n ; i++){
maxi[powe][i] = max(maxi[powe - 1][i] , maxi[powe - 1][ rmqt[powe - 1][i] ]);
if (rmqc[powe-1][i] && rmqc[powe-1][ rmqt[powe - 1][i] ]){
fth = rmqt[powe-1][i];
for (j = 0 ; j < v[fth].size() ; j++){
vecin = v[fth][j].first;
if (vecin != tt[fth].first && query(i , vecin) == vecin){
if (v[fth][j].second < tt[rmqt[powe-1][i]].second)
rmqc[powe][i] = 1;
break;
}
}
}
if (rmqd[powe-1][i] && rmqd[powe-1][ rmqt[powe - 1][i] ]){
fth = rmqt[powe-1][i];
for (j = 0 ; j < v[fth].size() ; j++){
vecin = v[fth][j].first;
if (vecin != tt[fth].first && query(i , vecin) == vecin){
if (v[fth][j].second > tt[rmqt[powe-1][i]].second)
rmqd[powe][i] = 1;
break;
}
}
}
}
}
/// momentul sa rasp la queryuri?
for (i = 1 ; i <= cnt ; i++){
x = qry[i].x;
y = qry[i].y;
mch = qry[i].mch;
fth = query(x , y);
if (qmaxi(x , fth) > mch || qmaxi(y , fth) > mch){
fprintf (fout,"no\n"); /// maximul prea mare
continue;
}
if (ok(x , y , fth))
fprintf (fout,"yes\n");
else fprintf (fout,"no\n");
}
return 0;
}
Compilation message
servers.cpp: In function 'void dfs(int, int, int, int)':
servers.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (i = 0 ; i < v[nod].size() ; i++){
| ~~^~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:206:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for (j = 0 ; j < v[fth].size() ; j++){
| ~~^~~~~~~~~~~~~~~
servers.cpp:224:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
224 | for (j = 0 ; j < v[fth].size() ; j++){
| ~~^~~~~~~~~~~~~~~
servers.cpp:130:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | fscanf (fin,"%d%d\n",&n,&q);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:136:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | fscanf (fin,"%d%d\n",&x,&y);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:144:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | fscanf (fin,"%d%d\n",&x,&y);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
5580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
5580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
5592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
5592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
5640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
5640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
