oj.uz

Submission #36827

# Submission time Handle Problem Language Result Execution time Memory
36827 2017-12-15T19:24:11 Z alenam0161 Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 89 ms 29892 KB 
#include <bits/stdc++.h>

using namespace std;
#define ad push_back
const int N =200007;
vector<int> g[N],loop;
using ll=long long;
void add(pair<int,ll>& aa,pair<int,ll>bb){
    if(aa.first<bb.first)aa=bb;
    else if(aa.first==bb.first)aa.second+=bb.second;
}
pair<int,ll> ans;
int par[N];
bool used[N];
bool gta=false;
void dfs0(int v,int p){
    if(gta)return;
par[v]=p;
used[v]=true;
for(int to:g[v]){
    if(gta)return;
    if(to==p)continue;
    if(used[to]){
        int r=v;
        while(true){
            loop.ad(r);
            if(r==to)break;
            r=par[r];
        }
        gta=true;
        return;
    }
    else dfs0(to,v);
}
}
pair<int,ll> dfs_upd(int v,int p){
pair<int,ll> cur={0,1};
for(int to:g[v]){
    if(to==p)continue;
    if(used[to])continue;
    pair<int,ll> w=dfs_upd(to,v);
    w.first++;
    add(ans,{cur.first+w.first,cur.second*w.second});
    add(cur,w);
}
return cur;
}
pair<int,ll> dp[N];
int t=0;
pair<int,ll> Mx[N*4];
void build(int l,int r,int v){
if(l==r){
    Mx[v]=dp[l];
    return;
}
int m=(l+r)/2;
build(l,m,v+v);
build(m+1,r,v+v+1);
add(Mx[v],Mx[v+v]);
add(Mx[v],{(m-l+1)+Mx[v+v+1].first,Mx[v+v+1].second});
}
pair<int,ll> get(int l,int r,int v,int tl,int tr,int qan=0){
if(tl<=l&&r<=tr)
        return {Mx[v].first+qan,Mx[v].second};
int m=(l+r)/2;
pair<int,ll> e={0,0};
if(tl<=m)add(e,get(l,m,v+v,tl,tr,qan));
if(tr>m){
    add(e,get(m+1,r,v+v+1,tl,tr,qan+max(0,m-tl+1)));
}
return e;
}
int main()
{
  //  freopen("input.txt","r",stdin);
 //   freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].ad(v);
        g[v].ad(u);
    }
    dfs0(1,1);
    memset(used,0,sizeof(used));
    for(int to:loop)used[to]=true;
    for(int to:loop){
       dp[t++]=dfs_upd(to,to);
    }
    for(int i=0;i<t;++i){
        dp[i+t]=dp[i];
    }
    int len=t+t;
    build(0,len,1);
    int erk=t/2;
    for(int i=0;i<t;++i){
        pair<int,ll> z=get(0,len,1,i+1,i+erk,1);
        z=max(dp[i],{dp[i].first+z.first,dp[i].second*z.second});
        add(ans,z);
    }
    cout<<ans.second<<endl;
    return 0;
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:81:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&u,&v);
                            ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23304 KB Output is correct
2 Correct 0 ms 23304 KB Output is correct
3 Correct 0 ms 23304 KB Output is correct
4 Correct 0 ms 23304 KB Output is correct
5 Correct 0 ms 23304 KB Output is correct
6 Incorrect 0 ms 23304 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 23304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 26340 KB Output is correct
2 Correct 79 ms 26736 KB Output is correct
3 Incorrect 79 ms 29892 KB Output isn't correct
4 Halted 0 ms 0 KB -