#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 240000
#define costo first
#define des second
struct x {
lli tipo;
lli des;
lli tiempo;
lli id;
};
lli n,qq,a,b,cent,cont,t;
lli visitados[MAX+2],tam[MAX+2],llego[MAX+2],bit[MAX+2];
char c;
queue<lli> cola;
vector<pair<lli,lli> > hijos[MAX+2];
vector<x> querys[MAX+2];
pair<lli,lli> res[MAX+2];
void actualiza(lli pos,lli val) {
while (pos <= t) {
bit[pos] += val;
pos += pos&(-pos);
}
}
lli sum(lli pos) {
lli r = 0;
while (pos > 0) {
r += bit[pos];
pos -= pos&(-pos);
}
return r;
}
lli buscaCen (lli pos, lli padre, lli mitad) {
for (auto h : hijos[pos]){
if (h.des == padre || visitados[h.des] == 1) continue;
if (tam[h.des] > mitad) return buscaCen(h.des, pos, mitad);
}
return pos;
}
void DFS(lli pos, lli padre) {
tam[pos] = 1;
for (auto h : hijos[pos]) {
if (h.des == padre || visitados[h.des] == 1) continue;
DFS(h.des, pos);
tam[pos] += tam[h.des];
}
}
void ami(lli pos, lli padre, lli ant, vector<lli> &nuevos) {
nuevos.push_back(pos);
for (auto h : hijos[pos]) {
if (h.des == padre || visitados[h.des] == 1) continue;
if (h.costo > ant) continue;
ami(h.des,pos,h.costo,nuevos);
}
}
void aellos(lli pos, lli padre, lli ant, vector<pair<lli,lli> > & acc) {
acc.push_back({pos,ant});
for (auto h : hijos[pos]) {
if (h.des == padre || visitados[h.des] == 1) continue;
if (h.costo < ant) continue;
aellos(h.des,pos,h.costo,acc);
}
}
void solve() {
lli act;
while (!cola.empty()) {
act = cola.front();
cola.pop();
DFS(act,0);
cent = buscaCen(act,0,tam[act]/2);
sort(hijos[cent].begin(), hijos[cent].end());
reverse(hijos[cent].begin(),hijos[cent].end());
vector < pair<lli,lli> > deshacer;
for (auto h : hijos[cent]) {
if (visitados[h.des] == 1) continue;
vector<lli> nuevos;
ami(h.des,cent,h.costo,nuevos);
for (auto nodo : nuevos) {
for (auto q : querys[nodo]) {
if (q.tipo == 1) {
if (q.des == cent && q.tiempo < h.costo) res[q.id].second = 1;
else if (llego[q.des] > 0 && llego[q.des] < q.tiempo) res[q.id].second = 1;
}
else {
res[q.id].second += sum(q.tiempo);
if (h.costo < q.tiempo) res[q.id].second++;
}
}
}
vector< pair<lli,lli> > accesibles;
aellos(h.des,cent,h.costo,accesibles);
for ( auto nodo : accesibles) {
deshacer.push_back(nodo);
llego[nodo.first] = nodo.second;
actualiza(nodo.second,1);
}
}
for (auto q : querys[cent]) {
if (q.tipo == 1) {
if (llego[q.des] > 0 && llego[q.des] < q.tiempo) res[q.id].second = 1;
}
else {
res[q.id].second += sum(q.tiempo);
}
}
for (auto borr : deshacer) {
llego[borr.first] = 0;
actualiza(borr.second,-1);
}
visitados[cent] = 1;
for (auto h : hijos[cent]) {
if (visitados[h.des] == 1) continue;
cola.push(h.des);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> qq;
t = n+qq-1;
cont = 1;
rep(i,1,t){
cin >> c;
if (c == 'S') {
cin >> a >> b;
hijos[a].push_back({i,b});
hijos[b].push_back({i,a});
}
else if (c == 'Q') {
cin >> a >> b;
querys[b].push_back({1,a,i,cont});
res[cont].first = 1;
if (a == b) res[cont].second = 1;
cont++;
}
else {
cin >> a;
querys[a].push_back({2,0,i,cont});
res[cont].first = 2;
cont++;
}
}
cola.push(1);
solve();
cont--;
rep(i,1,cont) {
if (res[i].first == 2) cout << res[i].second+1 << "\n";
else {
if (res[i].second == 1) cout << "yes\n";
else cout << "no\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
19824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
19824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
19888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
19888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
19776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
19776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
19840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
19840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
19808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
19808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
19864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
19864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
