| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 17956 | Adilkhan | Shymbulak (IZhO14_shymbulak) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define fname ""
#define sz(x) (int)(x.size())
#define int long long
typedef long long ll;
using namespace std;
const ll N = (ll)(5e5) + 322;
const ll INF = (ll)(1e9);
const ll mod = (ll)(1e9) + 7;
const double eps = 1e-9;
int d[N][2], n, m, mx, sum;
vector <int> v[N];
queue <int> q;
void fmbfs(int s) {
memset(d, -1, sizeof d);
for (int i = 1; i <= n; ++i) d[i][1] = 0;
q.push(s);
d[s][0] = 0; d[s][1] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto to : v[x]) {
if (d[to][0] == -1) {
d[to][0] = d[x][0] + 1;
d[to][1] += d[x][1];
q.push(to);
continue;
}
if (d[to][0] == d[x][0] + 1) {
d[to][1] += d[x][1];
}
}
}
for (int i = 1; i <= n; ++i) {
mx = max(mx, d[i][0]);
}
}
bool bfs(int s) {
int z = sum;
memset(d, -1, sizeof d);
for (int i = 1; i <= n; ++i) d[i][1] = 0;
q.push(s);
d[s][0] = 0; d[s][1] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto to : v[x]) {
if (d[to][0] == -1) {
d[to][0] = d[x][0] + 1;
d[to][1] += d[x][1];
q.push(to);
continue;
}
if (d[to][0] == d[x][0] + 1) {
d[to][1] += d[x][1];
}
}
}
for (int i = 1; i <= n; ++i) {
if (mx == d[i][0]) {
sum += d[i][1];
}
}
return (z == sum);
}
main () {
// freopen(fname".in", "r", stdin);
//freopen(fname".out", "w", stdout);
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
int x, y; scanf("%lld%lld", &x, &y);
v[x].pb(y); v[y].pb(x);
}
for (int i = 1; i <= n; ++i) {
fmbfs(i);
}
for (int i = 1; i <= n; ++i) {
if (!bfs(i)) {
v[i].clear();
}
}
printf("%lld", sum / 2);
return 0;
}