#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
int low[DIM],niv[DIM],f[DIM],st[DIM],elem,sol;
int w[DIM];
vector <int> v[DIM],s[DIM];
pair <int , long long> lnt[DIM];
pair <int , long long> aint[DIM];
int lzy[DIM];
int solmax;
long long nr;
void dfs (int nod,int tata){
int i,vecin;
low[nod]=niv[nod];
st[++elem]=nod;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin!=tata){
if (!niv[vecin]){
niv[vecin]=1+niv[nod];
dfs (vecin,nod);
low[nod]=min(low[nod],low[vecin]);
///VERIFICARE
if (low[vecin]>=niv[nod]){
sol++;
do{
s[sol].push_back(st[elem]);
elem--;
}while (st[elem+1]!=vecin);
s[sol].push_back(nod);
}
}
else low[nod]=min(low[nod],niv[vecin]);
}
}
}
void dfs2 (int nod , int tt){
int i , vecin;
/// first e lantul maxim , second e diametrul max din subarb
lnt[nod] = make_pair(1 , 1);
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i];
if (f[vecin] || vecin == tt)
continue; /// nu
dfs2(vecin , nod);
if (lnt[vecin].first + lnt[nod].first > solmax){
solmax = lnt[vecin].first + lnt[nod].first;
nr = 2 * lnt[nod].second * lnt[vecin].second;
}
else if (lnt[vecin].first + lnt[nod].first == solmax){
nr = nr + 2 * lnt[nod].second * lnt[vecin].second;
}
if (lnt[vecin].first + 1 > lnt[nod].first){
lnt[nod].first = lnt[vecin].first + 1;
lnt[nod].second = lnt[vecin].second;
}
else if (lnt[vecin].first + 1 == lnt[nod].first){
lnt[nod].second += lnt[vecin].second;
}
}
}
inline void lazy_update (int nod,int st,int dr){
if (!lzy[nod]) /// nu ii trb lazy
return;
if (st<dr){ /// nu e frunza
lzy[2*nod]+=lzy[nod]; /// pass lazy
lzy[2*nod+1]+=lzy[nod];
}
aint[nod].first+=lzy[nod];
lzy[nod]=0;
}
void build (int nod , int st , int dr , int len){
int mid = (st + dr) / 2;
if (st == dr){
aint[nod] = make_pair(lnt[w[st]].first + min(st - 1 , len - st + 1) , lnt[w[st]].second);
return;
}
build (2 * nod , st , mid , len);
build (2 * nod + 1 , mid + 1 , dr , len);
if (aint[2 * nod].first > aint[2 * nod].second)
aint[nod] = aint[2 * nod];
else if (aint[2 * nod].first < aint[2 * nod].second)
aint[nod] = aint[2 * nod + 1];
else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);
}
void query (int nod , int st , int dr , int l , int r , int start){
int mid = (st + dr) / 2;
lazy_update (nod,st,dr);
if (l <= st && dr <= r){
//if (start == 1)
// printf ("%d " , aint[nod].first + lnt[w[start]].first - 1);
if (solmax < aint[nod].first + lnt[w[start]].first - 1){
solmax = aint[nod].first + lnt[w[start]].first - 1;
nr = aint[nod].second * lnt[w[start]].second;
}
else if (solmax == aint[nod].first + lnt[w[start]].first - 1)
nr += aint[nod].second * lnt[w[start]].second;
return;
}
if (l <= mid)
query(2 * nod , st , mid , l , r , start);
if (mid + 1 <= r)
query(2 * nod + 1 , mid + 1 ,dr , l , r , start);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
}
void update (int nod , int st , int dr , int l , int r , int val){
int mid = (st + dr) / 2;
lazy_update (nod,st,dr);
if (l <= st && dr <= r){
lzy[nod] += val;
lazy_update (nod,st,dr);
return;
}
if (l <= mid)
update(2 * nod , st , mid , l , r , val);
if (mid + 1 <= r)
update(2 * nod + 1 , mid + 1 ,dr , l , r , val);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
if (aint[2 * nod].first > aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod];
else if (aint[2 * nod].first < aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod + 1];
else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);
}
void upd_fr (int nod , int st , int dr ,int x , int val){
int mid = (st + dr) / 2;
lazy_update (nod,st,dr);
if (st == dr){
if (val == 1)
aint[nod].second *= 2;
else aint[nod].second /= 2;
return;
}
if (x <= mid)
upd_fr(2 * nod , st , mid , x , val);
else upd_fr(2 * nod + 1 , mid + 1 ,dr , x , val);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
if (aint[2 * nod].first > aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod];
else if (aint[2 * nod].first < aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod + 1];
else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , x , y , i , dmax , j , len , middle , nod;
long long frq;
fscanf (fin,"%d",&n);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
/// pasul 1: gaseste ciclul
for (i=1;i<=n;i++){
if (!niv[i]){
niv[i]=1;
dfs (i,0);
}
}
/// comp biconexa cu + 2 noduri
for (i = 1 ; i <= sol ; i++){
if (s[i].size() > 2){ /// asta !!
for (j = 0 ; j < s[i].size() ; j++){
w[j + 1] = s[i][j];
f[s[i][j]] = 1;
}
len = s[i].size();
}
}
for (i = 1 ; i <= len ; i++)
dfs2(w[i] , 0);
/// pt fiecare nod din ciclu, construiesti diametrul + lantul maxim
build (1 , 1 , len , len);
/// daca distamta maxima = diametru maxim, mai adaugi si frq
if (len % 2 == 0){ /// cazul cand middle are 2 frecvente
upd_fr (1 , 1 , len , 1 + len / 2 , 1);
query (1 , 1 , len , 2 , len , 1);
middle = 1 + len / 2;
for (i = 2 ; i <= len ; i++){
/// updatezi intervale
nod = i;
middle++;
if (middle > len)
upd_fr (1 , 1 , len , middle - len , 1);
else
upd_fr (1 , 1 , len , middle , 1);
if (middle - 1 > len)
upd_fr (1 , 1 , len , middle - 1 - len , -1);
else
upd_fr (1 , 1 , len , middle - 1 , -1);
/// intre nod si middle - 1 scazi 1
if (middle - 1 < len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 1 , nod - 1 , 1);
update (1 , 1 , len , middle , len , 1);
}
else if (middle - 1 == len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 1 , nod - 1 , 1);
}
else {
update (1 , 1 , len , nod , len , -1);
update (1 , 1 , len , 1 , middle - 1 - len , -1);
update (1 , 1 , len , middle - len , nod - 1 , 1);
}
/// query
query (1 , 1 , len , 1 , i - 1 , i);
if (i != len)
query (1 , 1 , len , i + 1 , len , i);
}
}
else {
//solmax = nr = 0;
query (1 , 1 , len , 2 , len , 1);
middle = len / 2 + 1;
for (i = 2 ; i <= len ; i++){
/// updatezi intervale
nod = i;
middle++;
if (middle == len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 1 , nod - 1 , 1);
}
else if (middle == len + 1){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 2 , nod - 1 , 1);
}
else if (middle < len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , middle + 1 , len , 1);
update (1 , 1 , len , 1 , nod - 1 , 1);
}
else {
update (1 , 1 , len , nod , len , -1);
update (1 , 1 , len , 1 , middle - 1 - len , -1);
update (1 , 1 , len , middle + 1 - len , nod - 1 , 1);
}
/// query
query (1 , 1 , len , 1 , i - 1 , i);
if (i != len)
query (1 , 1 , len , i + 1 , len , i);
}
}
nr /= 2;
fprintf (fout,"%lld",nr);
return 0;
}
Compilation message
shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (i=0;i<v[nod].size();i++){
| ~^~~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int)':
shymbulak.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (i = 0 ; i < v[nod].size() ; i++){
| ~~^~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:223:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for (j = 0 ; j < s[i].size() ; j++){
| ~~^~~~~~~~~~~~~
shymbulak.cpp:199:25: warning: unused variable 'dmax' [-Wunused-variable]
199 | int n , x , y , i , dmax , j , len , middle , nod;
| ^~~~
shymbulak.cpp:200:15: warning: unused variable 'frq' [-Wunused-variable]
200 | long long frq;
| ^~~
shymbulak.cpp:201:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
201 | fscanf (fin,"%d",&n);
| ~~~~~~~^~~~~~~~~~~~~
shymbulak.cpp:203:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
203 | fscanf (fin,"%d%d",&x,&y);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
shymbulak.cpp:289:13: warning: 'len' may be used uninitialized in this function [-Wmaybe-uninitialized]
289 | if (i != len)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9708 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 4 |
Correct |
8 ms |
9836 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
19024 KB |
Output is correct |
| 2 |
Correct |
88 ms |
19820 KB |
Output is correct |
| 3 |
Correct |
147 ms |
25580 KB |
Output is correct |
| 4 |
Incorrect |
65 ms |
19940 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
