#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
const int maxn=2e5+5, Log=18, pot=(1<<Log);
struct tournament{
int t[pot*2];
double k[pot*2];
int prop[pot*2];
void propagate(int x){
if(!prop[x]){
return;
}
t[x]+=prop[x];
if(x<pot){
prop[x*2]+=prop[x];
prop[x*2+1]+=prop[x];
}
prop[x]=0;
}
void cisti(int L, int D, int x, int val){
propagate(x);
if(L==val && D==val){
return;
}
if((L+D)/2>=val){
cisti(L, (L+D)/2, x*2, val);
}
else{
cisti((L+D)/2+1, D, x*2+1, val);
}
}
void update1(int x, int val, double komb){
cisti(0, pot-1, 1, x-pot);
t[x]=val;
k[x]=komb;
for(x/=2; x>0; x/=2){
propagate(x*2);
propagate(x*2+1);
if(t[x*2]>t[x*2+1]){
t[x]=t[x*2];
k[x]=k[x*2];
}
else if(t[x*2]<t[x*2+1]){
t[x]=t[x*2+1];
k[x]=k[x*2+1];
}
else{
t[x]=t[x*2];
k[x]=k[x*2]+k[x*2+1];
}
}
}
void update(int x, int val){
t[x]+=val;
for(x/=2; x>0; x/=2){
propagate(x*2);
propagate(x*2+1);
if(t[x*2]>t[x*2+1]){
t[x]=t[x*2];
k[x]=k[x*2];
}
else if(t[x*2]<t[x*2+1]){
t[x]=t[x*2+1];
k[x]=k[x*2+1];
}
else{
t[x]=t[x*2];
k[x]=k[x*2]+k[x*2+1];
}
}
}
void update2(int L, int D, int x, int l, int d, int val){
propagate(x);
if(L>=l && D<=d){
update(x, val);
if(x<pot){
prop[x*2]+=val;
prop[x*2+1]+=val;
}
return;
}
if((L+D)/2>=l){
update2(L, (L+D)/2, x*2, l, d, val);
}
if((L+D)/2+1<=d){
update2((L+D)/2+1, D, x*2+1, l, d, val);
}
}
};
vector < int > ms[maxn];
bitset < maxn > bio;
vector < int > sad;
vector < int > da;
bitset < maxn > cik;
tournament T;
bool ciklus(int x, int prosl){
if(bio[x]){
bool p=0;
for(int i=0; i<(int)sad.size(); i++){
if(sad[i]==x){
p=1;
}
if(p){
da.push_back(sad[i]);
cik[sad[i]]=1;
}
}
return 1;
}
sad.push_back(x);
bio[x]=1;
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]!=prosl){
if(ciklus(ms[x][i], x)){
return 1;
}
}
}
bio[x]=0;
sad.pop_back();
return 0;
}
vector < int > dulj;
void siri(int x, int dep){
// cout << "proso " << x << endl;
bio[x]=1;
dulj.push_back(dep);
for(int i=0; i<(int)ms[x].size(); i++){
if(!cik[ms[x][i]] && !bio[ms[x][i]]){
siri(ms[x][i], dep+1);
}
}
}
vector < array < double, 4 > > svi;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int a, b;
for(int i=0; i<n; i++){
cin >> a >> b;
a--;
b--;
ms[a].push_back(b);
ms[b].push_back(a);
}
ciklus(0, 0);
bio.reset();
/* for(int i=0; i<n; i++){
if(cik[i]){
cout << i << ' ';
}
}
cout << endl;*/
int br1, br2;
int val1, val2;
int pos;
int m=da.size();
for(int i=0; i<m; i++){
// cout << da[i] << ' ';
siri(da[i], 0);
sort(dulj.begin(), dulj.end());
br1=0;
pos=dulj.size()-1;
val1=dulj.back();
while(pos>-1 && val1==dulj[pos]){
br1++;
pos--;
}
if(br1>1){
svi.push_back({val1, br1, val1, (double)(br1-1)/2});
}
else{
if(pos==-1){
val2=0;
}
else{
val2=dulj[pos];
}
br2=0;
while(pos>-1 && val2==dulj[pos]){
br2++;
pos--;
}
br2=max(br2, 1);
svi.push_back({val1, br1, val2, br2});
}
dulj.clear();
}
// cout << endl;
/* for(int i=0; i<m; i++){
cout << svi[i][0] << ' ' << svi[i][1] << ' ' << svi[i][2] << ' ' << svi[i][3] << endl;
}*/
int l1, d1, l2, d2;
for(int i=0; i<m; i++){
if(m&1){
T.update1(i+pot, svi[i][0], svi[i][1]);
}
else{
T.update1(i+pot, svi[i][0], svi[i][1]*2);
}
}
int maksi=0;
ll komb=0;
int val;
for(int i=0; i<m; i++){
T.update1(i+pot, svi[i][2], svi[i][3]);
if(!i){
for(int j=1; j<m; j++){
T.update2(0, pot-1, 1, j, j, min(j, m-j));
}
}
else{
l1=i-m/2;
d1=i-1;
if(l1<0){
l2=l1+m;
d2=m-1;
l1=0;
T.update2(0, pot-1, 1, l2, d2, 1);
}
T.update2(0, pot-1, 1, l1, d1, 1);
l1=i;
d1=i+m/2-1;
if(d1>=m){
l2=0;
d2=d1-m;
d1=m-1;
T.update2(0, pot-1, 1, l2, d2, -1);
}
T.update2(0, pot-1, 1, l1, d1, -1);
}
val=T.t[1]+svi[i][0];
// cout << val << ' ' << svi[i][1] << ' ' << T.k[1] << endl;
if(val>maksi){
maksi=val;
komb=T.k[1]*svi[i][1];
}
else if(val==maksi){
komb+=T.k[1]*svi[i][1];
}
T.update1(i+pot, -maxn, 0);
}
cout << komb << '\n';
// cout << maksi << endl;
return 0;
}
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:196:19: warning: narrowing conversion of 'val1' from 'int' to 'double' [-Wnarrowing]
196 | svi.push_back({val1, br1, val1, (double)(br1-1)/2});
| ^~~~
shymbulak.cpp:196:25: warning: narrowing conversion of 'br1' from 'int' to 'double' [-Wnarrowing]
196 | svi.push_back({val1, br1, val1, (double)(br1-1)/2});
| ^~~
shymbulak.cpp:196:30: warning: narrowing conversion of 'val1' from 'int' to 'double' [-Wnarrowing]
196 | svi.push_back({val1, br1, val1, (double)(br1-1)/2});
| ^~~~
shymbulak.cpp:211:19: warning: narrowing conversion of 'val1' from 'int' to 'double' [-Wnarrowing]
211 | svi.push_back({val1, br1, val2, br2});
| ^~~~
shymbulak.cpp:211:25: warning: narrowing conversion of 'br1' from 'int' to 'double' [-Wnarrowing]
211 | svi.push_back({val1, br1, val2, br2});
| ^~~
shymbulak.cpp:211:30: warning: narrowing conversion of 'val2' from 'int' to 'double' [-Wnarrowing]
211 | svi.push_back({val1, br1, val2, br2});
| ^~~~
shymbulak.cpp:211:36: warning: narrowing conversion of 'br2' from 'int' to 'double' [-Wnarrowing]
211 | svi.push_back({val1, br1, val2, br2});
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5060 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5072 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5196 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
8680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
