#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
const int inf = 1e9 + 7;
struct DSU {
vi par;
vi subSize;
vector<set<int>> data;
void init(int n) {
par.resize(n + 1);
subSize.resize(n + 1);
data.resize(n + 1);
for (int i = 1; i <= n; i++) {
par[i] = i;
subSize[i] = 1;
data[i].insert(i);
}
}
int findSet(int v) {
if (v == par[v]) return v;
return findSet(par[v]);
}
bool unite(int v, int u) {
int pv = findSet(v);
int pu = findSet(u);
if (pv == pu)return false;
if (subSize[pv] > subSize[pu]) swap(pv, pu);
par[pv] = pu;
subSize[pu] += subSize[pv];
bool swaped = false;
if (data[pv].size() > data[pu].size()) {
swap(pv, pu);
swaped = true;
}
auto it = data[pv].begin();
for (int i = 0; i < data[pv].size(); i++) {
data[pu].insert(*it);
it++;
}
if (swaped) {
swap(data[pv], data[pu]);
}
return true;
}
bool query(int v, int d) {
int pv = findSet(v);
auto it = data[pv].find(d);
if (it == data[pv].end()) return false;
return true;
}
int count(int d) {
int pv = findSet(d);
int ans = subSize[pv];
return ans;
}
};
struct LCA {
vvp graph;
vvi table;
vi timeIn;
vi timeOut;
vp par;
int log;
int timer = 0;
void dfs(int v, int p, int w) {
par[v] = { p,w };
table[v][0] = p;
timeIn[v] = timer;
timer++;
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
int w = graph[v][i].second;
if (u != p) {
dfs(u, v, w);
}
}
timeOut[v] = timer;
timer++;
}
void preCalc(int root, int n, vvp& g) {
log = ceil(log2(n));
graph = g;
timeIn.resize(n + 1);
timeOut.resize(n + 1);
par.resize(n + 1);
table.resize(n + 1, vi(log + 1));
timer = 0;
dfs(root, root, -1);
for (int i = 1; i <= log; i++) {
for (int v = 1; v <= n; v++) {
int p = table[v][i - 1];
table[v][i] = table[p][i - 1];
}
}
}
bool isAncestor(int a, int b) {
if (timeIn[a] <= timeIn[b] && timeOut[a] >= timeOut[b]) {
return true;
}
return false;
}
int findLCA(int a, int b) {
if (isAncestor(a, b))return a;
if (isAncestor(b, a))return b;
for (int i = log; i >= 0; i--) {
if (!isAncestor(table[a][i], b)) {
a = table[a][i];
}
}
return table[a][0];
}
};
struct CENTROID
{
vvp graph;
vi subSize;
int n;
void init(int N, vvp& g) {
n = N;
graph = g;
subSize.resize(n + 1);
dfs(1, 1);
}
void dfs(int v, int p) {
subSize[v] = 1;
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
if (u != p) {
dfs(u, v);
subSize[v] += subSize[u];
}
}
}
int getCentroid(int v, int p) {
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
if (u != p && subSize[u] > n / 2) {
return getCentroid(u, v);
}
}
return v;
}
};
vvp graph;
LCA lca;
vp topUpI;
vp topUpD;
bool incresingPath(int a, int b) {
int p = lca.findLCA(a, b);
bool oka = false;
bool okb = false;
int topa = topUpD[a].first;
int topb = topUpI[b].first;
if (lca.isAncestor(topa, p)) oka = true;
if (lca.isAncestor(topb, p)) okb = true;
int lasta = -1;
int lastb = -1;
if (a != p) {
lasta = topUpD[a].second;
}
if (b != p) {
lastb = topUpD[b].second;
}
/*
int lasta = -1;
int lastb = -1;
if (a != p) {
int lastw = lca.par[a].second;
a = lca.par[a].first;
while (a != p)
{
int currw = lca.par[a].second;
if (currw < lastw) {
oka = false;
return false;
}
a = lca.par[a].first;
lastw = currw;
}
lasta = lastw;
}
if (b != p) {
int lastw = lca.par[b].second;
b = lca.par[b].first;
while (b != p)
{
int currw = lca.par[b].second;
if (currw > lastw) {
okb = false;
return false;
}
b = lca.par[b].first;
lastw = currw;
}
lastb = lastw;
}
if (lasta != -1 && lastb != -1 && lastb < lasta) return false;
*/
if (lasta != -1 && lastb != -1 && lastb > lasta) return false;
if (oka && okb) return true;
return false;
}
void dfs(int v, int p, int wpD, int wpI) {
if (topUpI[v].first == -1) {
topUpI[v].first = v;
wpI = -1;
}
if (topUpD[v].first == -1) {
topUpD[v].first = v;
wpD = -1;
}
for (int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i].first;
int w = graph[v][i].second;
if (u != p) {
if (wpI == -1) {
topUpI[u] = topUpI[v];
topUpI[u].second = w;
}
else {
if (w < wpI) {
topUpI[u] = topUpI[v];
}
}
if (wpD == -1) {
topUpD[u] = topUpD[v];
topUpD[u].second = w;
}
else {
if (w > wpD) {
topUpD[u] = topUpD[v];
}
}
dfs(u, v, w, w);
}
}
}
void solve() {
int n, k;
cin >> n >> k;
graph.resize(n + 1);
topUpI.resize(n + 1, { -1,-1 });
topUpD.resize(n + 1, { -1, -1 });
DSU dsu;
dsu.init(n);
char t;
int a, b;
int timer = 1;
vector<pair<char, pii>> queries;
for (int i = 0; i < n + k - 1; i++) {
cin >> t;
if (t == 'S') {
cin >> a >> b;
queries.push_back({ t,{a,b} });
graph[a].push_back({ b,timer });
graph[b].push_back({ a,timer });
timer++;
}
if (t == 'Q') {
cin >> a >> b;
queries.push_back({ t,{a,b} });
}
if (t == 'C') {
cin >> a;
queries.push_back({ t,{a,a} });
}
}
CENTROID c;
c.init(n, graph);
int centroid = c.getCentroid(1, 1);
dfs(centroid, centroid, -1, -1);
lca.preCalc(centroid, n, graph);
for (int i = 0; i < queries.size(); i++) {
t = queries[i].first;
a = queries[i].second.first;
b = queries[i].second.second;
if (t == 'S') {
dsu.unite(a, b);
}
if (t == 'Q') {
bool connected = dsu.findSet(a) == dsu.findSet(b);
bool ans = false;
if (connected) {
ans = incresingPath(a, b);
}
if (ans) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
}
if (t == 'C') {
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Compilation message
servers.cpp: In member function 'bool DSU::unite(int, int)':
servers.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < data[pv].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'void LCA::dfs(int, int, int)':
servers.cpp:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'void CENTROID::dfs(int, int)':
servers.cpp:165:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'int CENTROID::getCentroid(int, int)':
servers.cpp:175:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'void dfs(int, int, int, int)':
servers.cpp:268:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
268 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'void solve()':
servers.cpp:338:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<char, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
338 | for (int i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
2232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
2232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
2340 KB |
Output is correct |
| 2 |
Correct |
483 ms |
60444 KB |
Output is correct |
| 3 |
Correct |
463 ms |
60512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
2340 KB |
Output is correct |
| 2 |
Correct |
483 ms |
60444 KB |
Output is correct |
| 3 |
Correct |
463 ms |
60512 KB |
Output is correct |
| 4 |
Incorrect |
155 ms |
2248 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
2224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
2224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
2236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
2236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
2252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
2284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
2284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
