#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
const int inf = int(1e9);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#define _LOCAL _DEBUG
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
const int maxn = int(1.5e5);
int tin[maxn];
int tout[maxn];
int timer = 0;
int up[maxn][18];
bool upincreasing[maxn][18];
bool updecreasing[maxn][18];
int upmax[maxn][18];
int upmin[maxn][18];
int upv[maxn];
int depth[maxn];
void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
depth[u] = depth[p] + 1;
tin[u] = timer++;
up[u][0] = p;
upmax[u][0] = upv[u];
upmin[u][0] = upv[u];
upincreasing[u][0] = upmax[u][0] < upmax[p][0] || p == 0 || u == 0;
updecreasing[u][0] = upmax[u][0] > upmax[p][0] || p == 0 || u == 0;
repp(d, 1, 18)
{
int mid = up[u][d - 1];
up[u][d] = up[mid][d - 1];
upmax[u][d] = max(upmax[u][d - 1], upmax[mid][d - 1]);
upmin[u][d] = min(upmin[u][d - 1], upmin[mid][d - 1]);
upincreasing[u][d] = upincreasing[u][d - 1] && upincreasing[mid][d - 1] && (upmax[mid][0] < upmax[up[mid][0]][0] || up[mid][0] == 0 || mid == 0);
updecreasing[u][d] = updecreasing[u][d - 1] && updecreasing[mid][d - 1] && (upmax[mid][0] > upmax[up[mid][0]][0] || up[mid][0] == 0 || mid == 0);
}
repe(e, edges[u]) if (e.first != p)
{
upv[e.first] = e.second;
dfs(e.first, u, p1, _p2, edges);
}
tout[u] = timer++;
}
bool isancestor(int a, int b)
{
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int pathmax(int a, int b)
{
if (isancestor(a, b)) return -1;
int ret = -1;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[a][d], b))
{
ret = max(ret, upmax[a][d]);
a = up[a][d];
}
}
return max(ret, upmax[a][0]);
}
int pathmin(int a, int b)
{
if (isancestor(a, b)) return inf;
int ret = inf;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[a][d], b))
{
ret = min(ret, upmin[a][d]);
a = up[a][d];
}
}
return min(ret, upmin[a][0]);
}
int lca(int a, int b)
{
if (isancestor(a, b)) return a;
if (isancestor(b, a)) return b;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[a][d], b))
{
a = up[a][d];
}
}
return up[a][0];
}
struct Centroid
{
int n;
vvi edges;
vi vis;
vi par;
vi size;
Centroid() {}
Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n), par(n), size(n)
{
init_centroid(0, -1);
}
int find_centroid(int u, int p, int n)
{
repe(e, edges[u])
{
if (e == p) continue;
if (!vis[e] && size[e] > n / 2) return find_centroid(e, u, n);
}
return u;
}
int find_size(int u, int p)
{
if (vis[u]) return 0;
size[u] = 1;
repe(e, edges[u])
{
if (e == p) continue;
size[u] += find_size(e, u);
}
return size[u];
}
void init_centroid(int u, int p)
{
find_size(u, u);
int c = find_centroid(u, u, size[u]);
vis[c] = 1;
par[c] = p;
repe(e, edges[c])
{
if (!vis[e]) init_centroid(e, c);
}
}
};
int cdepth[maxn];
void d(int u, int p, vvi& adj)
{
cdepth[u] = cdepth[p] + 1;
repe(e, adj[u]) if (e != p) d(e, u, adj);
}
signed main()
{
fast();
//ifstream in("C:\\Users\\Matis\\desktop\\comp_prog\\x64\\debug\\in.txt");
//cin.rdbuf(in.rdbuf());
int n, q;
cin >> n >> q;
vvi queries;
int t = 0;
vector<vector<p2>> edges(n);
vector<p2> edgelist;
vvi e(n);
rep(i, n + q - 1)
{
char c;
cin >> c;
if (c == 'S')
{
int a, b;
cin >> a >> b;
a--; b--;
edgelist.push_back(p2(a, b));
edges[a].push_back(p2(b, t));
edges[b].push_back(p2(a, t));
e[a].push_back(b);
e[b].push_back(a);
t++;
}
else if (c == 'Q')
{
int a, b;
cin >> a >> b;
a--; b--;
queries.push_back({ 0, b, a, t - 1 });
}
else
{
int c;
cin >> c;
c--;
queries.push_back({ 1, c, -1, t - 1 });
}
}
depth[0] = 0;
dfs(0, 0, -1, -1, edges);
Centroid cent(e);
auto getmax = [&](int a, int b)
{
return max(pathmax(a, b), pathmax(b, a));
};
auto getmin = [&](int a, int b)
{
return min(pathmin(a, b), pathmin(b, a));
};
auto pathgood = [&](int a, int b, int t)
{
if (getmax(a, b) > t) return false;
// all edges <= t
// from b->lca increasing
// from a->lca decreasing
bool good = 1;
int u = b;
int prev = inf;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[u][d], a))
{
good &= updecreasing[u][d];
u = up[u][d];
}
}
if (!isancestor(u, a))
{
prev = upmax[u][0];
}
u = a;
int v = -1;
for (int d = 17; d >= 0; d--)
{
if (!isancestor(up[u][d], b))
{
good &= upincreasing[u][d];
u = up[u][d];
}
}
if (!isancestor(u, b))
{
v = upmax[u][0];
}
return good && (v < prev);
};
vector<map<int, int>> children(n);
vi centroidpar = cent.par;
vector<vector<p2>> enableat(n + 2);
rep(i, n)
{
int u = centroidpar[i];
int prev = i;
while (u != -1)
{
if (pathgood(u, i, inf)) enableat[getmax(u, i)].emplace_back(prev, getmin(i, u));
prev = u;
u = centroidpar[u];
}
}
int timer = 0;
repe(q, queries)
{
int type = q[0], a = q[1], b = q[2], t = q[3];
if (type == 0)
{
cout << (pathgood(a, b, t) ? "yes" : "no") << "\n";
}
else
{
while (timer <= t)
{
repe(e, enableat[timer])
{
children[centroidpar[e.first]][e.second]++;
}
timer++;
}
int ans = 0;
repe(c, children[a]) ans += c.second;
int u = a;
int prev = u;
while (centroidpar[u]!=-1)
{
prev = u;
u = centroidpar[u];
if (pathgood(a, u, t))
{
ans++;
int v = getmax(a, u);
repe(c, children[u]) if (c.first > v) ans += c.second;
}
}
cout << ans + 1 << "\n";
}
}
return 0;
}
Compilation message
servers.cpp: In constructor 'Centroid::Centroid(vvi&)':
servers.cpp:119:9: warning: 'Centroid::edges' will be initialized after [-Wreorder]
119 | vvi edges;
| ^~~~~
servers.cpp:118:9: warning: 'int Centroid::n' [-Wreorder]
118 | int n;
| ^
servers.cpp:125:5: warning: when initialized here [-Wreorder]
125 | Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n), par(n), size(n)
| ^~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:316:17: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
316 | int prev = u;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
18684 KB |
Output is correct |
2 |
Correct |
44 ms |
22248 KB |
Output is correct |
3 |
Correct |
43 ms |
22528 KB |
Output is correct |
4 |
Correct |
55 ms |
22524 KB |
Output is correct |
5 |
Correct |
67 ms |
22852 KB |
Output is correct |
6 |
Correct |
42 ms |
22352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
18684 KB |
Output is correct |
2 |
Correct |
44 ms |
22248 KB |
Output is correct |
3 |
Correct |
43 ms |
22528 KB |
Output is correct |
4 |
Correct |
55 ms |
22524 KB |
Output is correct |
5 |
Correct |
67 ms |
22852 KB |
Output is correct |
6 |
Correct |
42 ms |
22352 KB |
Output is correct |
7 |
Correct |
33 ms |
18432 KB |
Output is correct |
8 |
Correct |
65 ms |
22112 KB |
Output is correct |
9 |
Correct |
186 ms |
22644 KB |
Output is correct |
10 |
Correct |
111 ms |
22588 KB |
Output is correct |
11 |
Correct |
148 ms |
22528 KB |
Output is correct |
12 |
Correct |
789 ms |
22580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
18548 KB |
Output is correct |
2 |
Correct |
195 ms |
84716 KB |
Output is correct |
3 |
Correct |
195 ms |
84912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
18548 KB |
Output is correct |
2 |
Correct |
195 ms |
84716 KB |
Output is correct |
3 |
Correct |
195 ms |
84912 KB |
Output is correct |
4 |
Correct |
33 ms |
18444 KB |
Output is correct |
5 |
Execution timed out |
3546 ms |
89692 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
18436 KB |
Output is correct |
2 |
Correct |
614 ms |
102100 KB |
Output is correct |
3 |
Correct |
587 ms |
101992 KB |
Output is correct |
4 |
Correct |
633 ms |
109932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
18436 KB |
Output is correct |
2 |
Correct |
614 ms |
102100 KB |
Output is correct |
3 |
Correct |
587 ms |
101992 KB |
Output is correct |
4 |
Correct |
633 ms |
109932 KB |
Output is correct |
5 |
Correct |
30 ms |
18432 KB |
Output is correct |
6 |
Correct |
841 ms |
107076 KB |
Output is correct |
7 |
Correct |
945 ms |
115008 KB |
Output is correct |
8 |
Correct |
1006 ms |
106724 KB |
Output is correct |
9 |
Correct |
989 ms |
107148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
18392 KB |
Output is correct |
2 |
Correct |
322 ms |
89660 KB |
Output is correct |
3 |
Correct |
358 ms |
84084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
18392 KB |
Output is correct |
2 |
Correct |
322 ms |
89660 KB |
Output is correct |
3 |
Correct |
358 ms |
84084 KB |
Output is correct |
4 |
Correct |
32 ms |
18428 KB |
Output is correct |
5 |
Correct |
476 ms |
95076 KB |
Output is correct |
6 |
Correct |
483 ms |
89640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
18360 KB |
Output is correct |
2 |
Correct |
583 ms |
101748 KB |
Output is correct |
3 |
Correct |
568 ms |
101824 KB |
Output is correct |
4 |
Correct |
640 ms |
110004 KB |
Output is correct |
5 |
Correct |
33 ms |
18440 KB |
Output is correct |
6 |
Correct |
330 ms |
89996 KB |
Output is correct |
7 |
Correct |
401 ms |
84020 KB |
Output is correct |
8 |
Correct |
528 ms |
85084 KB |
Output is correct |
9 |
Correct |
510 ms |
85440 KB |
Output is correct |
10 |
Correct |
1062 ms |
94180 KB |
Output is correct |
11 |
Correct |
1160 ms |
92876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
18360 KB |
Output is correct |
2 |
Correct |
583 ms |
101748 KB |
Output is correct |
3 |
Correct |
568 ms |
101824 KB |
Output is correct |
4 |
Correct |
640 ms |
110004 KB |
Output is correct |
5 |
Correct |
33 ms |
18440 KB |
Output is correct |
6 |
Correct |
330 ms |
89996 KB |
Output is correct |
7 |
Correct |
401 ms |
84020 KB |
Output is correct |
8 |
Correct |
528 ms |
85084 KB |
Output is correct |
9 |
Correct |
510 ms |
85440 KB |
Output is correct |
10 |
Correct |
1062 ms |
94180 KB |
Output is correct |
11 |
Correct |
1160 ms |
92876 KB |
Output is correct |
12 |
Correct |
30 ms |
18304 KB |
Output is correct |
13 |
Correct |
824 ms |
107124 KB |
Output is correct |
14 |
Correct |
938 ms |
114820 KB |
Output is correct |
15 |
Correct |
1022 ms |
107052 KB |
Output is correct |
16 |
Correct |
975 ms |
106672 KB |
Output is correct |
17 |
Correct |
33 ms |
18444 KB |
Output is correct |
18 |
Correct |
450 ms |
95180 KB |
Output is correct |
19 |
Correct |
492 ms |
89408 KB |
Output is correct |
20 |
Correct |
765 ms |
90420 KB |
Output is correct |
21 |
Correct |
650 ms |
90424 KB |
Output is correct |
22 |
Correct |
1695 ms |
97432 KB |
Output is correct |
23 |
Correct |
1689 ms |
103804 KB |
Output is correct |
24 |
Correct |
1312 ms |
102664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
18488 KB |
Output is correct |
2 |
Correct |
45 ms |
22296 KB |
Output is correct |
3 |
Correct |
44 ms |
22404 KB |
Output is correct |
4 |
Correct |
57 ms |
22520 KB |
Output is correct |
5 |
Correct |
67 ms |
22784 KB |
Output is correct |
6 |
Correct |
43 ms |
22272 KB |
Output is correct |
7 |
Correct |
33 ms |
18436 KB |
Output is correct |
8 |
Correct |
202 ms |
84456 KB |
Output is correct |
9 |
Correct |
210 ms |
84616 KB |
Output is correct |
10 |
Correct |
28 ms |
18408 KB |
Output is correct |
11 |
Correct |
585 ms |
101752 KB |
Output is correct |
12 |
Correct |
621 ms |
101752 KB |
Output is correct |
13 |
Correct |
628 ms |
109320 KB |
Output is correct |
14 |
Correct |
32 ms |
18432 KB |
Output is correct |
15 |
Correct |
335 ms |
86972 KB |
Output is correct |
16 |
Correct |
366 ms |
81328 KB |
Output is correct |
17 |
Correct |
551 ms |
82484 KB |
Output is correct |
18 |
Correct |
538 ms |
82492 KB |
Output is correct |
19 |
Correct |
1022 ms |
91172 KB |
Output is correct |
20 |
Correct |
1297 ms |
89880 KB |
Output is correct |
21 |
Correct |
270 ms |
83944 KB |
Output is correct |
22 |
Correct |
230 ms |
85108 KB |
Output is correct |
23 |
Correct |
350 ms |
85648 KB |
Output is correct |
24 |
Correct |
351 ms |
79732 KB |
Output is correct |
25 |
Correct |
726 ms |
89740 KB |
Output is correct |
26 |
Correct |
494 ms |
78004 KB |
Output is correct |
27 |
Correct |
403 ms |
77496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
18488 KB |
Output is correct |
2 |
Correct |
45 ms |
22296 KB |
Output is correct |
3 |
Correct |
44 ms |
22404 KB |
Output is correct |
4 |
Correct |
57 ms |
22520 KB |
Output is correct |
5 |
Correct |
67 ms |
22784 KB |
Output is correct |
6 |
Correct |
43 ms |
22272 KB |
Output is correct |
7 |
Correct |
33 ms |
18436 KB |
Output is correct |
8 |
Correct |
202 ms |
84456 KB |
Output is correct |
9 |
Correct |
210 ms |
84616 KB |
Output is correct |
10 |
Correct |
28 ms |
18408 KB |
Output is correct |
11 |
Correct |
585 ms |
101752 KB |
Output is correct |
12 |
Correct |
621 ms |
101752 KB |
Output is correct |
13 |
Correct |
628 ms |
109320 KB |
Output is correct |
14 |
Correct |
32 ms |
18432 KB |
Output is correct |
15 |
Correct |
335 ms |
86972 KB |
Output is correct |
16 |
Correct |
366 ms |
81328 KB |
Output is correct |
17 |
Correct |
551 ms |
82484 KB |
Output is correct |
18 |
Correct |
538 ms |
82492 KB |
Output is correct |
19 |
Correct |
1022 ms |
91172 KB |
Output is correct |
20 |
Correct |
1297 ms |
89880 KB |
Output is correct |
21 |
Correct |
270 ms |
83944 KB |
Output is correct |
22 |
Correct |
230 ms |
85108 KB |
Output is correct |
23 |
Correct |
350 ms |
85648 KB |
Output is correct |
24 |
Correct |
351 ms |
79732 KB |
Output is correct |
25 |
Correct |
726 ms |
89740 KB |
Output is correct |
26 |
Correct |
494 ms |
78004 KB |
Output is correct |
27 |
Correct |
403 ms |
77496 KB |
Output is correct |
28 |
Correct |
43 ms |
10344 KB |
Output is correct |
29 |
Correct |
66 ms |
18172 KB |
Output is correct |
30 |
Correct |
182 ms |
18252 KB |
Output is correct |
31 |
Correct |
105 ms |
20220 KB |
Output is correct |
32 |
Correct |
158 ms |
20612 KB |
Output is correct |
33 |
Correct |
819 ms |
22264 KB |
Output is correct |
34 |
Correct |
33 ms |
18444 KB |
Output is correct |
35 |
Execution timed out |
3537 ms |
87196 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |