oj.uz

Submission #36828

# Submission time Handle Problem Language Result Execution time Memory
36828 2017-12-15T19:35:00 Z alenam0161 Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 206 ms 30568 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-max(l,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.first<<endl;
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Correct 0 ms 23304 KB Output is correct
7 Correct 0 ms 23304 KB Output is correct
8 Correct 0 ms 23304 KB Output is correct
9 Correct 0 ms 23304 KB Output is correct
10 Correct 3 ms 23304 KB Output is correct
11 Correct 3 ms 23304 KB Output is correct
12 Correct 0 ms 23304 KB Output is correct
13 Correct 0 ms 23304 KB Output is correct
14 Correct 0 ms 23304 KB Output is correct
15 Correct 0 ms 23304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23304 KB Output is correct
2 Correct 0 ms 23304 KB Output is correct
3 Correct 3 ms 23304 KB Output is correct
4 Correct 0 ms 23304 KB Output is correct
5 Correct 3 ms 23436 KB Output is correct
6 Correct 6 ms 23568 KB Output is correct
7 Correct 0 ms 23436 KB Output is correct
8 Correct 9 ms 23436 KB Output is correct
9 Correct 3 ms 23436 KB Output is correct
10 Correct 0 ms 23436 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 26340 KB Output is correct
2 Correct 89 ms 26736 KB Output is correct
3 Correct 53 ms 29892 KB Output is correct
4 Correct 63 ms 26472 KB Output is correct
5 Correct 53 ms 26604 KB Output is correct
6 Correct 206 ms 28980 KB Output is correct
7 Correct 156 ms 28056 KB Output is correct
8 Correct 99 ms 29640 KB Output is correct
9 Correct 106 ms 29772 KB Output is correct
10 Correct 89 ms 30224 KB Output is correct
11 Correct 116 ms 30304 KB Output is correct
12 Correct 113 ms 30568 KB Output is correct