#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"
#define int long long
using namespace std;
const int N = 5002;
int n, X, Y, X2, Y2, parent[N], sz[N], d[N][N], d1[N][N], d2[N][N], ans;
bool used[N][N], used1[N][N], used2[N][N], c[N][N];
pair <int, int> ed[N];
vector <int> q[N];
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 v) {
queue <int> t;
t.push(v);
used[v][v] = true;
while (!t.empty()) {
int z = t.front();
t.pop();
for (auto i : q[z]) {
if (used[v][i])
continue;
used[v][i] = true;
d[v][i] = d[v][z] + 1;
t.push(i);
}
}
}
void bfs1(int v) {
queue <int> t;
t.push(v);
used1[v][v] = true;
while (!t.empty()) {
int z = t.front();
t.pop();
for (auto i : q[z]) {
if (used1[v][i])
continue;
c[v][i] = c[v][z];
if ((z == X && i == Y) || (z == Y && i == X)) {
c[v][i] = true;
}
used1[v][i] = true;
d1[v][i] = d1[v][z] + 1;
t.push(i);
}
}
}
void del(int x, int 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;
}
}
}
void add(int x, int 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());
}
void bfs2(int v) {
queue <int> t;
t.push(v);
used2[v][v] = true;
while (!t.empty()) {
int z = t.front();
t.pop();
for (auto i : q[z]) {
if (used2[v][i])
continue;
used2[v][i] = true;
d2[v][i] = d2[v][z] + 1;
t.push(i);
}
}
}
signed 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;
ed[i] = {x, y};
if (find_set(x) == find_set(y)) {
X = x, Y = y;
continue;
}
q[x].pb(y);
q[y].pb(x);
union_set(x, y);
}
for (int i = 1; i <= n; i++) {
make_set(i);
}
for (int i = n; i >= 1; i--) {
int x = ed[i].fi, y = ed[i].se;
if (find_set(x) == find_set(y)) {
X2 = x, Y2 = y;
continue;
}
union_set(x, y);
}
add(X, Y);
for (int i = 1; i <= n; i++) {
bfs(i);
}
del(X2, Y2);
for (int i = 1; i <= n; i++) {
bfs1(i);
}
add(X2, Y2);
del(X, Y);
for (int i = 1; i <= n; i++) {
bfs2(i);
}
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
res = max(res, d[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (d[i][j] == res) {
ans++;
if (c[i][j] && d[i][j] == d2[i][j] && d[i][j] == d1[i][j]) {
ans++;
}
}
}
}
cout<<ans;
}
Compilation message
shymbulak.cpp: In function 'void del(long long int, long long int)':
shymbulak.cpp:80:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q[x].size(); i++) {
~~^~~~~~~~~~~~~
shymbulak.cpp:86: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 |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
33656 KB |
Output is correct |
| 2 |
Correct |
61 ms |
40932 KB |
Output is correct |
| 3 |
Incorrect |
106 ms |
55800 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
