#include <bits/stdc++.h>
/*
Things need to accomplish :
- Finding LCA : done
- Have time_in, time_out : done
- Decompose into components of demands from predec to ancestor : done
- Bipartiting
*/
using namespace std;
#define int long long
typedef pair <int, int> ii;
const int N = 3e5 + 5, MOD = 1e9 + 7, lg = 26;
int n, m, d[N], tin[N], tout[N], P[N][lg], x[N], y[N], dfsTime, par[2 * N];
vector <int> adj[N];
bool inGraph[N * 2]; // Create a new graph, with nodes are edges and the compenents, they has edges if both points to the same direction
void prepare(int u, int pre) {
tin[u] = ++dfsTime;
if (~pre) d[u] = d[pre] + 1;
for (int v : adj[u]) {
if (v == pre) continue;
P[v][0] = u;
prepare(v, u);
}
tout[u] = ++dfsTime;
}
int lca(int u, int v, ii &tw) {
bool swapped = false;
if (d[v] > d[u]) {
swapped = true;
swap(u, v);
}
for (int i = lg - 1; i >= 0; --i) if ((1 << i) <= d[u] - d[v])
u = P[u][i];
if (u == v) return u;
for (int i = lg - 1; i >= 0; --i) if ((1 << i) <= d[u] && P[u][i] != P[v][i])
u = P[u][i], v = P[v][i];
if (swapped) swap(u, v);
tw.first = u, tw.second = v;
return P[u][0];
}
struct dsu_t {
int n;
vector <int> lab, sz;
dsu_t() {}
dsu_t(int _n) {
this -> n = _n;
sz.assign(n + 5, 1);
lab.assign(n + 5, -1);
}
int root(int x) {
return lab[x] == -1 ? x : lab[x] = root(lab[x]);
}
void merge(int u, int v) {
int x = root(u), y = root(v);
if (x == y) return;
lab[y] = x;
sz[x] += sz[y];
}
};
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= m; ++i) {
cin >> x[i] >> y[i];
}
prepare(1, -1);
for (int i = 1; i < lg; ++i) {
for (int u = 1; u <= n; ++u) {
P[u][i] = P[P[u][i - 1]][i - 1];
}
}
dsu_t one = dsu_t(n);
for (int i = 1; i <= m; ++i) {
int u = x[i], v = y[i];
if (tin[u] > tin[v]) swap(u, v);
if (!(tin[u] < tin[v] && tout[u] > tout[v])) continue;
u = one.root(u), v = one.root(v);
while (v != u) {
one.merge(P[v][0], v);
v = one.root(P[v][0]);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
42860 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
108652 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
398 ms |
96236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
366 ms |
95980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
382 ms |
96236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
389 ms |
96340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
