#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
const int N = 24e4 + 20;
vector<pair<int, int>> adj[N];
int ans[N], Cnt[N], gr[N], fir[N], last[N], fen[N];
vector<pair<int, int>> que1[N];
vector<int> que2[N];
bool hide[N], az[N], be[N];
int Cen;
int bads0[N], bads1[N];
int t0, t1;
pair<int, int> verts[N];
int vert_sz = 0;
int is_que[N];
inline void add(int i, int x)
{
i++;
for (; i < N; i += i & -i) fen[i] += x;
return;
}
inline int get(int i)
{
i++;
int ans = 0;
for (; i > 0; i -= i & -i) ans += fen[i];
return ans;
}
bool compa(pair<int, int> p1, pair<int, int> p2)
{
return (make_pair(fir[p1.F], p1.S) < make_pair(fir[p2.F], p2.S));
}
void init(int u, int pp = -1)
{
Cnt[u] = 1;
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F;
if (v != pp && !hide[u])
{
init(v, u);
Cnt[u] += Cnt[v];
}
}
return;
}
int find_cen(int u, int _n, int pp = -1)
{
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F;
if (v != pp && !hide[v] && Cnt[v] * 2 > _n) return find_cen(v, _n, u);
}
return u;
}
void dfs1(int u, int pp = -1)
{
if (az[u])
{
bads1[t1++] = u;
verts[vert_sz++] = {u, 1};
}
if (be[u])
{
bads0[t0++] = u;
verts[vert_sz++] = {u, 0};
}
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F, w = ppp.S;
if (hide[v] || v == pp) continue;
fir[v] = fir[u]; gr[v] = gr[u]; last[v] = w;
az[v] = be[v] = false;
if (w < last[u])
{
az[v] = az[u];
}
if (w > last[u])
{
be[v] = be[u];
}
dfs1(v, u);
}
return;
}
void dfs2(int u, int pp = -1)
{
for (pair<int, int> ppp : que1[u])
{
int v = ppp.F, qq = ppp.S;
if (v == Cen)
{
if (az[u] && fir[u] < qq) ans[qq] = 1;
continue;
}
if (gr[v] == -1) continue;
if (az[u] && be[v] && fir[u] < fir[v] && last[v] < qq) ans[qq] = 1;
}
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F;
if (!hide[v] && v != pp) dfs2(v, u);
}
return;
}
void dfs3(int u, int pp = -1)
{
gr[u] = -1;
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F;
if (!hide[v] && v != pp) dfs3(v, u);
}
return;
}
void decompose(int u)
{
//cout << " nwklngkneflweknfl nlkwnflnwl nkn " << gr[0] << '\n';
init(u);
u = find_cen(u, Cnt[u]);
assert(u == 0);
//cout << " " << u + 1 << '\n';
vert_sz = t0 = t1 = 0;
Cen = u;
int tttt = 1;
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F, w = ppp.S;
if (!hide[v])
{
fir[v] = w; last[v] = w; gr[v] = tttt++; az[v] = be[v] = true;
dfs1(v, u);
}
}
sort(verts, verts + vert_sz, compa);
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F;
if (!hide[v]) dfs2(v, u);
}
for (pair<int, int> ppp : que1[u])
{
int v = ppp.F, qq = ppp.S;
if (gr[v] == -1) continue;
if (be[v] && last[v] < qq) ans[qq] = 1;
}
for (int i = vert_sz - 1; i > -1; i--)
{
int x = verts[i].F, ff = verts[i].S;
if (ff == 0)
{
add(last[x], 1);
continue;
}
for (int qq : que2[x])
{
ans[qq] += get(qq - 1);
if (fir[x] < qq) ans[qq]++;
}
}
for (int qq : que2[u])
{
ans[qq] += get(qq - 1);
}
for (int i = 0; i < t0; i++)
{
add(last[bads0[i]], -1);
}
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F;
if (!hide[v]) dfs3(v, u);
}
hide[u] = true;
for (pair<int, int> ppp : adj[u])
{
int v = ppp.F;
if (!hide[v]) decompose(v);
}
return;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(gr, -1, sizeof gr);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n + k - 1; i++)
{
char cc;
cin >> cc;
if (cc == 'S')
{
int u, v;
cin >> u >> v;
u--; v--;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
continue;
}
if (cc == 'Q')
{
is_que[i] = 1;
int a, d;
cin >> a >> d;
a--; d--;
if (a == d)
{
ans[i] = 1;
continue;
}
que1[d].push_back({a, i});
continue;
}
int u;
cin >> u;
is_que[i] = 2;
u--;
que2[u].push_back(i);
}
decompose(0);
for (int i = 1; i <= n + k - 1; i++)
{
if (is_que[i] == 1)
{
if (ans[i] != 0) cout << "yes\n";
else cout << "no\n";
continue;
}
if (is_que[i] == 2) cout << ans[i] + 1 << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
40860 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
40860 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
42516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
42516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
40796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
40796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
40812 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
40812 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
40772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
40772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
40772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
40772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
