#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
using namespace std;
const int N = 2e5 + 3;
int n, parent[N], sz[N], d[2][N], deg[N], X, Y;
int up[18][N], tin[N], tout[N], timer, h[N], dist[N];
bool used[2][N], c[2][N];
vector <int> q[N], leaves;
void make_set(int x) {
parent[x] = x;
sz[x] = 1;
}
int find_set(int x) {
if (x == parent[x])
return x;
return parent[x] = find_set(parent[x]);
}
void union_set(int x, int y) {
x = find_set(x);
y = find_set(y);
if (x != y) {
if (sz[x] < sz[y])
swap(x, y);
parent[y] = x;
sz[x] += sz[y];
}
}
void bfs(int t, int v) {
queue <int> bq;
used[t][v] = true;
bq.push(v);
while (!bq.empty()) {
int z = bq.front();
bq.pop();
for (auto i : q[z]) {
if (used[t][i])
continue;
c[t][i] = c[t][z];
if ((z == X && i == Y) || (z == Y && i == X)) {
c[t][i] = true;
}
used[t][i] = true;
d[t][i] = d[t][z] + 1;
bq.push(i);
}
}
}
bool upper(int v, int u) {
return tin[v] <= tin[u] && tout[u] <= tout[v];
}
void dfs(int v, int p) {
h[v] = h[p] + 1;
tin[v] = ++timer;
up[0][v] = p;
for (int i = 1; i < 18; i++) {
up[i][v] = up[i - 1][up[i - 1][v]];
}
for (auto i : q[v]) {
if (i != p) {
dfs(i, v);
}
}
tout[v] = timer;
}
int lca(int v, int u) {
if (upper(v, u)) {
return v;
}
if (upper(u, v)) {
return u;
}
for (int i = 17; i >= 0; i--) {
if (!upper(up[i][v], u)) {
v = up[i][v];
}
}
return up[0][v];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for (int i = 1; i <= n; i++) {
make_set(i);
}
for (int i = 1; i <= n; i++) {
int x, y;
cin>>x>>y;
if (find_set(x) == find_set(y)) {
X = x, Y = y;
continue;
}
q[x].pb(y);
q[y].pb(x);
deg[x]++;
deg[y]++;
union_set(x, y);
}
q[X].push_back(Y);
swap(q[X].front(), q[X].back());
q[Y].push_back(X);
swap(q[Y].front(), q[Y].back());
for (int i = 1; i <= n; i++) {
if (deg[i] == 1) {
leaves.pb(i);
}
}
bfs(0, X);
bfs(1, Y);
for (int i = 0; i < q[X].size(); i++) {
if (q[X][i] == Y) {
q[X].erase(q[X].begin() + i);
break;
}
}
for (int i = 0; i < q[Y].size(); i++) {
if (q[Y][i] == X) {
q[Y].erase(q[Y].begin() + i);
break;
}
}
deg[X]--;
deg[Y]--;
dfs(1, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
int x = i, y = j, tmp = N, magic = 0;
if (upper(X, x) && !upper(X, y)) {
tmp = min(tmp, h[x] - h[X] + d[0][y]);
magic = c[0][y];
}
if (upper(X, y) && !upper(X, x)) {
tmp = min(tmp, h[y] - h[X] + d[0][x]);
magic = c[0][x];
}
if (upper(Y, x) && !upper(Y, y)) {
tmp = min(tmp, h[x] - h[Y] + d[1][y]);
magic = c[1][y];
}
if (upper(Y, y) && !upper(Y, x)) {
tmp = min(tmp, h[y] - h[Y] + d[1][x]);
magic = c[1][x];
}
if (tmp != N) {
if (tmp == h[x] + h[y] - 2 * h[lca(x, y)]) {
dist[tmp] += 1 + magic;
} else {
dist[tmp] += 1;
}
} else {
tmp = h[x] + h[y] - 2 * h[lca(x, y)];
dist[tmp] += 1;
}
}
}
dist[1]++;
for (int i = N - 1; i >= 0; i--) {
if (dist[i] > 0) {
return cout<<dist[i], 0;
}
}
}
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:126:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[X].size(); i++) {
~~^~~~~~~~~~~~~
shymbulak.cpp:132:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[Y].size(); i++) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
5368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1566 ms |
19572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
