#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <deque>
using namespace std;
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
const int inf = 2e9;
const int N = 5e3 + 15;
int n, tin[N], fup[N], last, parent[N], d[N], dist[N][N];
vector <int> g[N];
bool used[N], is[N], cycle[N], whole_cycle = true;
int vertex, cnt_cycle;
ll ans;
void find_points(int v, int p = -1) {
used[v] = true;
tin[v] = fup[v] = last++;
int child = 0;
for(int to : g[v]) {
if(to != p) {
if(used[to])
fup[v] = min(fup[v], tin[to]);
else {
find_points(to, v);
fup[v] = min(fup[v], fup[to]);
if(fup[to] >= tin[v] && p != -1)
is[v] = true;
++child;
}
}
}
if(child > 1 && p == -1)
is[v] = true;
}
bool find_cycle(int v, int p = -1) {
used[v] = true;
parent[v] = p;
for(int to : g[v]) {
if(to != p) {
if(used[to]) {
int u = v;
cycle[u] = true;
++cnt_cycle;
while(u != to) {
++cnt_cycle;
u = parent[u];
cycle[u] = true;
}
return true;
}
else if(find_cycle(to, v))
return true;
}
}
return false;
}
void bfs(int s) {
queue <int> q;
q.push(s);
memset(used, 0, sizeof(used));
used[s] = true;
while(!q.empty()) {
int v = q.front();
q.pop();
for(int to : g[v])
if(!used[to]) {
d[to] = d[v] + 1;
used[to] = true;
q.push(to);
}
}
}
void bfs_all(int s) {
queue <int> q;
q.push(s);
dist[s][s] = 0;
memset(used, 0, sizeof(used));
used[s] = true;
while(!q.empty()) {
int v = q.front();
q.pop();
for(int to : g[v])
if(!used[to]) {
dist[s][to] = dist[s][v] + 1;
used[to] = true;
q.push(to);
}
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
g[u].pb(v);
g[v].pb(u);
}
for(int i = 1; i <= n; ++i) {
if(g[i].size() != 2) {
whole_cycle = false;
break;
}
}
if(whole_cycle)
printf("%d\n", n);
else {
find_cycle(1);
memset(used, 0, sizeof(used));
find_points(1);
for(int i = 1; i <= n; ++i)
if(is[i] && cycle[i]) {
vertex = i;
break;
}
for(int i = 1; i <= n; ++i)
bfs_all(i);
int maxx = 0;
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
maxx = max(dist[i][j], maxx);
for(int i = 1; i <= n; ++i) {
for(int j = i + 1; j <= n; ++j) {
if(dist[i][j] == maxx) {
if((cnt_cycle & 1) || (!cycle[i] && !cycle[j]))
ans += 1;
else
ans += 2;
}
}
}
printf("%lld\n", ans);
}
return 0;
}
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
shymbulak.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
14 ms |
6264 KB |
Output is correct |
| 3 |
Incorrect |
26 ms |
8568 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1579 ms |
6668 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
