#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N = (int)2e5 + 7;
vector < int > gr[N];
int n;
int used[N], deg[N];
ll ans = 0;
int diam;
int dist[N], us[N], id[N];
vector < int > node;
void bfs(int v) {
memset(used, 0, sizeof used);
queue < int > q;
q.push(v);
used[v] = 1;
while (!q.empty()) {
v = q.front();
q.pop();
for (int to : gr[v]) {
if (used[to] == 0) {
used[to] = used[v] + 1;
q.push(to);
}
}
}
}
void bfs1(int v) {
memset(dist, 0, sizeof dist);
queue < int > q;
q.push(v);
dist[v] = 1;
int asd = v;
int res = 0;
int mx = 0;
while (!q.empty()) {
v = q.front();
q.pop();
for (int to : gr[v]) {
if (dist[to] == 0) {
dist[to] = dist[v] + 1;
mx = max(mx, dist[to]);
q.push(to);
} else if (dist[v] + 1 == dist[to]) {
res = id[to];
}
}
}
if (mx - 1 == diam) {
int val = 0;
for (int i = 1; i <= n; i++) {
if (mx == dist[i]) val++;
}
ans += val;
if (res) {
val = 0;
for (int i = 1; i <= n; i++) {
if (id[i] == res && dist[i] == mx) val++;
}
ans += val;
}
}
}
void dfs1(int v, int pr) {
node.push_back(v);
us[v] = 1;
for (int to : gr[v]) {
if (us[to] || used[to] != 2) continue;
dfs1(to, v);
}
}
void dfs2(int v, int pr) {
for (int to : gr[v]) {
if (to == pr || used[to] == 2) continue;
id[to] = id[v];
dfs2(to, v);
}
}
main() {
iota(id, id + N, 0);
cin >> n;
for (int i = 1; i <= n; i++) {
int u, v;
cin >> u >> v;
gr[u].push_back(v);
gr[v].push_back(u);
deg[u]++;
deg[v]++;
}
int mx = 0;
for (int i = 1; i <= n; i++) {
bfs(i);
for (int j = 1; j <= n; j++) {
mx = max(mx, used[j]);
}
}
diam = mx - 1;
for (int i = 1; i <= n; i++) {
if (gr[i].size() == 1) {
node.push_back(i);
}
}
memset(used, 0, sizeof used);
for (int i = 0; i < n; i++) {
if (i == node.size()) {
break;
}
int v = node[i];
used[v] = 1;
for (int to : gr[v]) {
if (!used[to]) {
deg[to]--;
if (deg[to] <= 1) {
node.push_back(to);
}
}
}
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
used[i] = 2;
}
}
while (!node.empty()) node.pop_back();
for (int i = 1; i <= n; i++) {
if (used[i] == 2) {
dfs1(i, i);
break;
}
}
for (int i = 1; i <= n; i++) {
if (used[i] == 2) {
dfs2(i, i);
}
}
for (int i = 1; i <= n; i++) {
bfs1(i);
}
cout << ans / 2;
}
Compilation message
shymbulak.cpp: In function 'void bfs1(long long int)':
shymbulak.cpp:40:6: warning: unused variable 'asd' [-Wunused-variable]
int asd = v;
^~~
shymbulak.cpp: At global scope:
shymbulak.cpp:89:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:115:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == node.size()) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9756 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9832 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9896 KB |
Output is correct |
| 6 |
Correct |
13 ms |
9896 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9896 KB |
Output is correct |
| 8 |
Correct |
13 ms |
9904 KB |
Output is correct |
| 9 |
Correct |
13 ms |
9924 KB |
Output is correct |
| 10 |
Correct |
12 ms |
9928 KB |
Output is correct |
| 11 |
Correct |
13 ms |
9932 KB |
Output is correct |
| 12 |
Correct |
12 ms |
9936 KB |
Output is correct |
| 13 |
Correct |
34 ms |
10000 KB |
Output is correct |
| 14 |
Correct |
92 ms |
10192 KB |
Output is correct |
| 15 |
Correct |
88 ms |
10192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
10192 KB |
Output is correct |
| 2 |
Correct |
141 ms |
10192 KB |
Output is correct |
| 3 |
Correct |
180 ms |
10192 KB |
Output is correct |
| 4 |
Correct |
185 ms |
10192 KB |
Output is correct |
| 5 |
Execution timed out |
1532 ms |
10464 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
14232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
