oj.uz

Submission #377324

# Submission time Handle Problem Language Result Execution time Memory
377324 2021-03-14T00:49:14 Z rrrr10000 Duathlon (APIO18_duathlon) C++14
0 / 100
 352 ms 38380 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
 

int main(){
    ll n,m;cin>>n>>m;
    vvp g(n);
    rep(i,m){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b,i);g[b].pb(a,i);
    }
    vi root,lk(n),dep(n,-1),gr_ver(n,-1),gr_edge(m,-1);
    vb is_kansetsu(n,false);
    function<ll(ll,ll,ll)> dfs0=[&](ll i,ll p,ll d){
        dep[i]=d;lk[i]=d;
        for(auto x:g[i])if(x.fi!=p){
            if(dep[x.fi]!=-1)chmin(lk[i],dep[x.fi]);
            else chmin(lk[i],dfs0(x.fi,i,d+1));
        }
        return lk[i];
    };rep(i,n)if(dep[i]==-1){dfs0(i,-1,0);root.pb(i);}
    ll cmp=0;
    function<void(ll,ll,ll)> dfs=[&](ll i,ll p,ll e){
        for(auto x:g[i])if(x.fi!=p){
            if(dep[x.fi]==dep[i]+1){
                if(lk[x.fi]>=dep[i])gr_edge[x.se]=cmp++;
                else gr_edge[x.se]=gr_edge[e];
                dfs(x.fi,i,x.se);
            }
            else if(dep[x.fi]<dep[i])gr_edge[x.se]=gr_edge[e];
        }
    };for(ll x:root)dfs(x,-1,-1);
    ll cmp_edge=cmp;
    rep(i,n){
        vi al;
        for(auto x:g[i])al.pb(gr_edge[x.se]);
        dupli(al);
        if(al.size()==0)gr_ver[i]=cmp++;
        else if(al.size()==1)gr_ver[i]=al[0];
        else{
            gr_ver[i]=cmp++;
            is_kansetsu[i]=true;
        }
    }
    vvi tree(cmp);
    rep(i,n)for(auto x:g[i])if(gr_edge[x.se]!=gr_ver[i]){
        tree[gr_edge[x.se]].pb(gr_ver[i]);
        tree[gr_ver[i]].pb(gr_edge[x.se]);
    }
    // outv(gr_ver);outv(gr_edge);
    rep(i,cmp)dupli(tree[i]);
    // outvv(tree);
    vi sz(cmp);
    rep(i,n)sz[gr_ver[i]]++;
    vi ch(cmp,-1);
    ll ans=n*(n-1)*(n-2);
    ll tmp;
    // out(cmp_edge);
    vi res(cmp);
    function<void(ll,ll)> slv=[&](ll i,ll p){
        ch[i]=sz[i];
        for(ll x:tree[i])if(x!=p){
            slv(x,i);
            ch[i]+=ch[x];
            if(i>=cmp_edge)ans-=res[x]*sz[i];
            else res[i]+=ch[x]*(ch[x]-1);
        }
    };
    function<void(ll,ll)> slv2=[&](ll i,ll p){
        if(i<cmp_edge){
            res[i]+=(tmp-ch[i])*(tmp-ch[i]-1);
            ans-=sz[i]*res[i];
        }
        else if(p!=-1){
            ans-=sz[i]*(res[p]-ch[i]*(ch[i]-1));
        }
        for(ll x:tree[i])if(x!=p){
            slv2(x,i);
        }
    };
    rep(i,cmp)if(ch[i]==-1){
        slv(i,-1);
        tmp=ch[i];
        slv2(i,-1);
    }
    out(ans);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 22044 KB Output is correct
2 Correct 185 ms 22020 KB Output is correct
3 Incorrect 234 ms 27628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Incorrect 2 ms 492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 23404 KB Output is correct
2 Correct 242 ms 23456 KB Output is correct
3 Correct 242 ms 23276 KB Output is correct
4 Correct 248 ms 23276 KB Output is correct
5 Correct 227 ms 23276 KB Output is correct
6 Correct 352 ms 38380 KB Output is correct
7 Correct 312 ms 33388 KB Output is correct
8 Correct 307 ms 30572 KB Output is correct
9 Correct 276 ms 28396 KB Output is correct
10 Incorrect 248 ms 23276 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 3 ms 620 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Incorrect 2 ms 492 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 23404 KB Output is correct
2 Correct 285 ms 24172 KB Output is correct
3 Correct 265 ms 23660 KB Output is correct
4 Correct 273 ms 22532 KB Output is correct
5 Correct 241 ms 18796 KB Output is correct
6 Correct 249 ms 17004 KB Output is correct
7 Correct 224 ms 15852 KB Output is correct
8 Correct 190 ms 14700 KB Output is correct
9 Correct 180 ms 14060 KB Output is correct
10 Correct 206 ms 13804 KB Output is correct
11 Correct 168 ms 13164 KB Output is correct
12 Correct 174 ms 12908 KB Output is correct
13 Correct 173 ms 12908 KB Output is correct
14 Correct 174 ms 15212 KB Output is correct
15 Correct 318 ms 34412 KB Output is correct
16 Correct 336 ms 31340 KB Output is correct
17 Correct 326 ms 31724 KB Output is correct
18 Correct 309 ms 28992 KB Output is correct
19 Incorrect 260 ms 22508 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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