#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;
const int maxn = 5001;
vector<vector<int> > v;
bitset<maxn> in_cycle;
int color[maxn];
int par[maxn];
int dpth[maxn];
int lift[maxn][16];
int num[maxn];
int pos_in_cycle[maxn];
vector<int> cycle;
int mx;
int ans;
void get_cycle(int u,int p = -1){
color[u] = 1;
par[u] = p;
for(int i(0); i < v[u].size();i++){
int to = v[u][i];
if(color[to] == 2)continue;
if(color[to] == 1 && to != par[u]){
int now = u;
in_cycle[to] = 1;
while(now!=to){
pos_in_cycle[now] = cycle.size();
cycle.push_back(now);
in_cycle[now] = 1;
now = par[now];
}
pos_in_cycle[now] = cycle.size();
cycle.push_back(now);
}else if(!color[to]){
get_cycle(to,u);
}
}
color[u] = 2;
}
void build_tree(int u,int p = -1){
if(p!=-1){
lift[u][0] = p;
dpth[u] = dpth[p]+1;
num[u] = num[p];
}else {
lift[u][0] = u;
}
for(int i(1); i < 16;i++){
lift[u][i] = lift[lift[u][i-1]][i-1];
}
for(int i(0); i < v[u].size();i++){
int to = v[u][i];
if(to == p || in_cycle[to])continue;
build_tree(to,u);
}
}
int get_lca(int x,int y){
if(dpth[x] > dpth[y])swap(x,y);
int delta = abs(dpth[x]-dpth[y]);
for(int i(0); i < 17;i++){
int bit = delta&(1<<i);
if(!bit)continue;
y = lift[y][i];
}
if(x == y)return x;
for(int i(15);i>=0;i--){
if(lift[x][i]!=lift[y][i]){
x = lift[x][i];
y = lift[y][i];
}
}
return lift[x][0];
}
int get_dist(int x,int y){
int dist = 0;
if(num[x] == num[y]){
int lca = get_lca(x,y);
dist = dpth[x]+dpth[y]-2*dpth[lca];
}else{
dist = dpth[x]+dpth[y];
int fst = pos_in_cycle[num[x]];
int snd = pos_in_cycle[num[y]];
if(fst > snd)swap(fst,snd);
int a = abs(snd-fst);
int b = cycle.size()-snd+fst;
dist+=min(a,b);
}
return dist;
}
void solve(int x,int y){
int dist = 0;
if(num[x] == num[y]){
int lca = get_lca(x,y);
dist = dpth[x]+dpth[y]-2*dpth[lca];
if(dist == mx)ans++;
}else{
dist = dpth[x]+dpth[y];
int fst = pos_in_cycle[num[x]];
int snd = pos_in_cycle[num[y]];
if(fst > snd)swap(fst,snd);
int a = abs(snd-fst);
int b = cycle.size()-snd+fst;
if(dist+a == mx && a == min(a,b)){
ans++;
//cout << "a " << x+1 << ' ' << y+1 << endl;
}
if(dist+b == mx && b == min(a,b)){
ans++;
//cout << "b " << x+1 << ' ' << y+1 << ' ' <<b << ' ' << dist << endl;
}
}
}
main(){
ios_base::sync_with_stdio(0);
int n; cin >> n;
v.resize(n+2);
for(int i(0); i < n;i++){
int a,b; cin >> a >> b;
a--;b--;
v[a].push_back(b);
v[b].push_back(a);
}
get_cycle(0,0);
for(int i(0); i < n;i++){
if(in_cycle[i]){
num[i] = i;
build_tree(i);
}
}
for(int i(0); i < n;i++){
for(int j(i+1); j < n;j++){
mx = max(mx,get_dist(i,j));
}
}
for(int i(0); i< n;i++){
for(int j(i+1); j < n;j++){
solve(i,j);
}
}
cout << ans;
return 0;
}
/*
*/
Compilation message
shymbulak.cpp: In function 'void get_cycle(int, int)':
shymbulak.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < v[u].size();i++){
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void build_tree(int, int)':
shymbulak.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < v[u].size();i++){
~~^~~~~~~~~~~~~
shymbulak.cpp: At global scope:
shymbulak.cpp:124:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
3 ms |
376 KB |
Output is correct |
| 14 |
Correct |
10 ms |
504 KB |
Output is correct |
| 15 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
39 ms |
504 KB |
Output is correct |
| 3 |
Correct |
7 ms |
504 KB |
Output is correct |
| 4 |
Correct |
27 ms |
504 KB |
Output is correct |
| 5 |
Correct |
241 ms |
1056 KB |
Output is correct |
| 6 |
Correct |
1417 ms |
1080 KB |
Output is correct |
| 7 |
Execution timed out |
1582 ms |
1016 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
11164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
