#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
const int MXN = 12e4 + 5;
const int mod = 1e9 + 7;
const int LOG = 20;
struct BIT
{
int n;
vector<int> ft;
void init(int N)
{
n = N + 5;
ft.assign(n + 5, 0);
}
void add(int pos, int val)
{
for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
}
int get(int pos, int res = 0)
{
for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
return res;
}
};
int n, m;
vector<array<int, 2>> adj[MXN];
int used[MXN], sz[MXN];
BIT ft[MXN];
int cent[LOG][MXN], w[LOG][MXN];
int ic[LOG][MXN], dc[LOG][MXN];
vector<array<int, 3>> ed;
array<int, 2> rep[LOG][MXN];
int tim;
void getsize(int a, int p)
{
sz[a] = 1;
for (array<int, 2> &v : adj[a])
{
if (used[v[0]] || v[0] == p) continue;
getsize(v[0], a);
sz[a] += sz[v[0]];
}
}
int findcent(int a, int p, int &curn)
{
for (array<int, 2> &v : adj[a])
{
if (used[v[0]] || v[0] == p) continue;
if (sz[v[0]] > curn / 2) return findcent(v[0], a, curn);
}
return a;
}
void dfs(int a, int p, int &lvl, int &cc, array<int, 2> &as)
{
rep[lvl][a] = as;
cent[lvl][a] = cc;
for (array<int, 2> &v : adj[a])
{
if (used[v[0]] || v[0] == p) continue;
w[lvl][v[0]] = v[1];
dfs(v[0], a, lvl, cc, as);
}
}
void maincent(int a, int lvl)
{
getsize(a, a);
int c = findcent(a, a, sz[a]);
ic[lvl][c] = dc[lvl][c] = 1;
used[c] = 1;
cent[lvl][c] = c;
for (array<int, 2> &v : adj[c])
{
if (used[v[0]]) continue;
w[lvl][v[0]] = v[1];
dfs(v[0], c, lvl, c, v);
}
for (array<int, 2> &v : adj[c])
{
if (used[v[0]]) continue;
maincent(v[0], lvl + 1);
}
}
int nw = 0;
void upd(int a, int p, int &lvl)
{
// if (!ic[lvl][a] && !dc[lvl][a]) return;
nw += ic[lvl][a];
for (array<int, 2> &v : adj[a])
{
if (cent[lvl][v[0]] != cent[lvl][a] || v[0] == p) continue;
if (v[1] > tim) continue;
ic[lvl][v[0]] = w[lvl][a] < v[1];
dc[lvl][v[0]] = w[lvl][a] > v[1];
upd(v[0], a, lvl);
}
}
int getind(int c, int ind)
{
int l = 0, r = (int)adj[c].size() - 1;
while (l < r)
{
int mid = (l + r) >> 1;
if (adj[c][mid][1] >= ind) r = mid;
else l = mid + 1;
}
return l;
}
void add(int c, int ind, int val)
{
ind = getind(c, ind);
ft[c].add(ind, val);
}
int ans;
void calcans(int a, int p, int w)
{
ans++;
for (array<int, 2> &v : adj[a])
{
if (v[0] == p || v[1] < w || v[1] > tim) continue;
calcans(v[0], a, v[1]);
}
}
int u1[MXN];
void trav(int a, int w)
{
u1[a] = 1;
for (array<int, 2> &v : adj[a])
{
if (u1[v[0]] || v[1] < w || v[1] > tim) continue;
trav(v[0], v[1]);
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
ed.resize(n + m - 1, {0, 0, 0});
for (array<int, 3> &e : ed)
{
char ch;
cin >> ch >> e[1];
if (ch == 'S')
{
cin >> e[2];
e[0] = 0;
}
else if (ch == 'Q')
{
cin >> e[2];
e[0] = 1;
}
else
{
e[0] = 2;
}
}
for (int i = 0; i < ed.size(); i++)
{
if (!ed[i][0]) adj[ed[i][1]].push_back({ed[i][2], i}), adj[ed[i][2]].push_back({ed[i][1], i});
}
for (int i = 1; i <= n; i++)
{
ft[i].init(adj[i].size());
}
maincent(1, 0);
for (tim = 0; tim < ed.size(); tim++)
{
array<int, 3> &e = ed[tim];
int x = e[1], y = e[2];
if (!e[0])
{
for (int i = 0; i < LOG; i++)
{
if (!cent[i][x] || !cent[i][y] || cent[i][x] != cent[i][y]) break;
nw = 0;
if (cent[i][x] == x)
{
ic[i][y] = 1;
dc[i][y] = 1;
upd(y, x, i);
if (nw) add(cent[i][y], rep[i][y][1], nw);
}
else if (cent[i][x] == y)
{
ic[i][x] = 1;
dc[i][x] = 1;
upd(x, y, i);
if (nw) add(cent[i][x], rep[i][x][1], nw);
}
else
{
int fx = 0, fy = 0;
if (ic[i][x] && w[i][x] < w[i][y]) ic[i][y] = 1, fy = 1;
else if (ic[i][y] && w[i][y] < w[i][x]) ic[i][x] = 1, fx = 1;
if (dc[i][x] && w[i][x] > w[i][y]) dc[i][y] = 1, fy = 1;
else if (dc[i][y] && w[i][y] > w[i][x]) dc[i][x] = 1, fx = 1;
if (fx)
{
upd(x, y, i);
if (nw) add(cent[i][x], rep[i][x][1], nw);
nw = 0;
}
if (fy)
{
upd(y, x, i);
if (nw) add(cent[i][x], rep[i][x][1], nw);
nw = 0;
}
// assert(fx + fy <= 1);
}
}
}
else if (e[0] == 1)
{
// fill(u1 + 1, u1 + n + 1, 0);
// trav(e[2], -inf);
// cout << (u1[e[1]] ? "yes" : "no") << endl;
int lg = -1;
for (int i = 0; i < LOG; i++)
{
if (!cent[i][x] || !cent[i][y] || cent[i][x] != cent[i][y])
{
lg = i - 1;
break;
}
}
assert(lg != -1);
int f = 0;
if (x == cent[lg][x]) f = 1;
else if (y == cent[lg][x]) f = 1;
else
{
int px = rep[lg][x][0], py = rep[lg][y][0];
f = w[lg][px] > w[lg][py];
}
cout << (ic[lg][x] && dc[lg][y] && f ? "yes\n" : "no\n");
}
else if (e[0] == 2)
{
ans = 0;
// for (int i = 0; i < LOG; i++)
// {
// if (!cent[i][x]) break;
// if (cent[i][x] == x) res += ft[x].get(adj[x].size()) + 1;
// else
// {
// if (dc[i][x])
// {
// int ind = getind(cent[i][x], rep[i][x][1]);
// res += ft[cent[i][x]].get(adj[cent[i][x]].size()) - ft[cent[i][x]].get(ind) + 1;
// }
// }
// }
calcans(e[1], e[1], -inf);
cout << ans << '\n';
}
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:171:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for (int i = 0; i < ed.size(); i++)
| ~~^~~~~~~~~~~
servers.cpp:180:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for (tim = 0; tim < ed.size(); tim++)
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
44372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
44372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
27980 KB |
Output is correct |
| 2 |
Correct |
75 ms |
56772 KB |
Output is correct |
| 3 |
Correct |
74 ms |
56772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
27980 KB |
Output is correct |
| 2 |
Correct |
75 ms |
56772 KB |
Output is correct |
| 3 |
Correct |
74 ms |
56772 KB |
Output is correct |
| 4 |
Correct |
18 ms |
27996 KB |
Output is correct |
| 5 |
Execution timed out |
3542 ms |
56592 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
50520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
50520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
50524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
50524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
50516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
50516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
44240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
44240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
