#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using pii = pair<int, int>;
#define fr first
#define sc second
struct Fenwick
{
int aib[120005];
vector<int> descos;
inline int lsb(int x)
{
return x & -x;
}
void update(int pos, int val)
{
descos.push_back(pos);
while(pos <= 120000)
aib[pos] += val, pos += lsb(pos);
}
int query(int pos)
{
int ans = 0;
while(pos)
ans += aib[pos], pos -= lsb(pos);
return ans;
}
void clean()
{
for(auto i : descos)
while(i <= 120000 && aib[i] != 0)
aib[i] = 0, i += lsb(i);
descos.clear();
}
} ds;
struct Intrebare
{
char ch;
int time, val; //daca e cazu
};
vector<Intrebare> qry[120005];
vector<pii> vec[120005];
bool viz[120005];
int answer[120005], sz[120005];
void dfsz(int nod, int papa)
{
int nsz = 1;
for(auto i : vec[nod])
if(i.fr != papa && !viz[i.fr])
dfsz(i.fr, nod), nsz += sz[i.fr];
sz[nod] = nsz;
}
int find_centroid(int nod, int szmx, int papa)
{
for(auto i : vec[nod])
if(!viz[i.fr] && i.fr != papa && sz[i.fr] >= (szmx + 1) / 2)
return find_centroid(i.fr, szmx, nod);
return nod;
}
int crdcr[120005], spretata[120005]; // &1 daca crescator, &2 daca descrescator
void dfs(int nod, int papa, vector<int> &baga, int primu = 0)
{
if(!primu)
{
crdcr[nod] = 0;
if(spretata[nod] <= spretata[papa])
crdcr[nod] ^= (1 & crdcr[papa]);
if(spretata[nod] >= spretata[papa])
crdcr[nod] ^= (2 & crdcr[papa]);
}
baga.push_back(nod);
for(auto i : vec[nod])
if(!viz[i.fr] && i.fr != papa)
dfs(i.fr, nod, baga), spretata[i.fr] = i.sc;
}
void dfs_centroid(int nod)
{
dfsz(nod, 0);
int centr = find_centroid(nod, sz[nod], 0);
crdcr[centr] = 3;
vector<pair<int, vector<int>>> realvec;
for(auto i : vec[centr])
if(!viz[i.fr])
{
realvec.push_back({i.fr, vector<int>(0)});
spretata[i.fr] = i.sc;
crdcr[i.fr] = 3;
dfs(i.fr, centr, realvec.back().sc, 1);
}
sort(all(realvec), [&](pair<int, vector<int>> a, pair<int, vector<int>> b)
{
return spretata[a.fr] < spretata[b.fr];
});
map<int, int> papsubctr, pospap;
for(auto i : realvec)
for(auto j : i.sc)
papsubctr[j] = i.fr;
for(int i = 0; i < realvec.size(); i ++)
pospap[realvec[i].fr] = i + 1;
for(int sus = realvec.size() - 1; sus >= 0; sus --)
{
auto i = realvec[sus];
ds.update(spretata[i.fr], 1);
if(sus != realvec.size() - 1)
ds.update(spretata[realvec[sus + 1].fr], -1);
for(auto j : i.sc)
for(auto k : qry[j])
{
if(k.ch == 'Q')
{
if(pospap[papsubctr[j]] < pospap[papsubctr[k.val]] && (crdcr[j] & 1) && (crdcr[k.val] & 2) && spretata[k.val] <= k.time)
answer[k.time] = -2;
}
else if(crdcr[j] & 1)
answer[k.time] += ds.query(k.time);
}
for(auto j : i.sc)
if(crdcr[j] & 2)
ds.update(spretata[j], 1);
}
//ar fi cazu sa verificam si pentru centroid queryurile
for(auto k : qry[centr])
{
if(k.ch == 'Q')
{
if(pospap[papsubctr[k.val]] && (crdcr[k.val] & 2) && spretata[k.val] <= k.time)
answer[k.time] = -2;
}
else
answer[k.time] += ds.query(k.time);
}
ds.clean();
viz[centr] = true;
for(auto i : vec[centr])
if(!viz[i.fr])
dfs_centroid(i.fr);
}
signed main()
{
int n, q;
cin >> n >> q;
for(int i = 1; i <= q + n - 1; i ++)
{
char ch;
cin >> ch;
if(ch == 'S')
{
int u, v;
cin >> u >> v;
vec[u].push_back({v, i});
vec[v].push_back({u, i});
answer[i] = -1;
}
if(ch == 'Q')
{
int u, v;
cin >> u >> v;
qry[u].push_back({'q', i, v});
answer[i] = -3;
}
if(ch == 'C')
{
int u;
cin >> u;
qry[u].push_back({'c', i, 0});
}
}
dfs_centroid(1);
for(int i = 1; i <= q + n - 1; i ++)
if(answer[i] != -1)
{
if(answer[i] >= 0)
cout << answer[i] + 1 << '\n';
else if(answer[i] == -2)
cout << "yes\n";
else
cout << "no\n";
}
}
Compilation message
servers.cpp: In function 'void dfs_centroid(int)':
servers.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0; i < realvec.size(); i ++)
| ~~^~~~~~~~~~~~~~~~
servers.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | if(sus != realvec.size() - 1)
| ~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
11272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
11272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
11336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
11336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
11336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
11336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
