oj.uz

Submission #250493

# Submission time Handle Problem Language Result Execution time Memory
250493 2020-07-18T08:05:26 Z rrrr10000 Duathlon (APIO18_duathlon) C++14
31 / 100
 246 ms 37096 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 all(a) a.begin(),a.end()
#define pb emplace_back
#define eb 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 dupli(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;
typedef multiset<ll> S;
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 noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
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;}

vvp g;
ll c,num;
vi id_ver,id_edge,lk,ord,tmp;
vb used,back_edge;
vi group;
void dfs(int i,int p){
    used[i]=true;
    group.pb(i);
    ord[i]=c++;
    lk[i]=ord[i];
    for(auto x:g[i]){
        if(x.fi!=p){
            if(ord[x.fi]<ord[i])tmp.pb(x.se);
            if(!used[x.fi]){
                dfs(x.fi,i);
                chmin(lk[i],lk[x.fi]);
                if(lk[x.fi]>=ord[i]){
                    while(true){
                        id_edge[tmp.back()]=num;
                        bool done=false;
                        if(tmp.back()==x.se)done=true;
                        tmp.pop_back();
                        if(done)break;
                    }
                    num++;
                }
            }
            else chmin(lk[i],ord[x.fi]);
        }
    }
}
vi f,sz,par;
vvi edge;
ll getsz(int i,int p){
    par[i]=p;
    if(i>=num)sz[i]=1;
    else sz[i]=f[i];
    for(ll x:edge[i])if(x!=p){
        sz[i]+=getsz(x,i);
    }
    return sz[i];
}
int main(){
    ll n,m,ans=0;cin>>n>>m;
    g=vvp(n);
    used=vb(n,false);
    lk=vi(n,inf);
    id_ver=vi(n,-2);
    id_edge=vi(m);
    back_edge=vb(m,false);
    ord=vi(n,-1);
    rep(i,m){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b,i);g[b].pb(a,i);
    }
    rep(i,n){
        if(used[i])continue;
        tmp=vi(0);
        group=vi(0);
        c=0;num=0;
        ll cnt=0;
        dfs(i,-1);
        if(group.size()<3)continue;
        f=vi(num);
        for(auto j:group){
            ll t=id_edge[g[j][0].se];
            for(auto x:g[j]){
                if(t!=id_edge[x.se])id_ver[j]=num+(cnt++);
            }
            if(id_ver[j]==-2){
                id_ver[j]=t;
                f[t]++;
            }
        }
        edge=vvi(num+cnt);
        for(ll x:group){
            if(id_ver[x]>=num)for(auto to:g[x]){
                edge[id_ver[x]].pb(id_edge[to.se]);
                edge[id_edge[to.se]].pb(id_ver[x]);
            }
        }
        rep(j,cnt+num)dupli(edge[j]);
        par=vi(num+cnt);sz=vi(num+cnt);
        getsz(0,-1);
        vi s(num);
        rep(j,num){
            for(ll x:edge[j])if(x!=par[j])s[j]+=sz[x]*(sz[x]-1);
            ans+=f[j]*((group.size()-1)*(group.size()-2)-s[j]);
            if(par[j]!=-1)ans-=f[j]*(group.size()-sz[j])*(group.size()-sz[j]-1);
        }
        REP(j,num,num+cnt){
            ans+=(group.size()-1)*(group.size()-2);
            for(ll x:edge[j])if(x!=par[j])ans-=s[x];
            ll p=par[j];
            ans-=(s[p]+(group.size()-sz[p])*(group.size()-sz[p]-1)-sz[j]*(sz[j]-1));
        }
    }
    out(ans);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 20580 KB Output is correct
2 Correct 157 ms 20708 KB Output is correct
3 Correct 209 ms 24264 KB Output is correct
4 Correct 198 ms 22800 KB Output is correct
5 Correct 165 ms 19964 KB Output is correct
6 Correct 230 ms 25696 KB Output is correct
7 Correct 184 ms 17692 KB Output is correct
8 Correct 212 ms 20960 KB Output is correct
9 Correct 212 ms 14424 KB Output is correct
10 Correct 175 ms 15644 KB Output is correct
11 Correct 150 ms 10744 KB Output is correct
12 Correct 156 ms 10616 KB Output is correct
13 Correct 128 ms 10220 KB Output is correct
14 Correct 122 ms 10104 KB Output is correct
15 Correct 107 ms 9080 KB Output is correct
16 Correct 113 ms 9080 KB Output is correct
17 Correct 8 ms 4992 KB Output is correct
18 Correct 8 ms 5120 KB Output is correct
19 Correct 9 ms 4992 KB Output is correct
20 Correct 8 ms 4992 KB Output is correct
21 Correct 9 ms 4992 KB Output is correct
22 Correct 9 ms 4992 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 26476 KB Output is correct
2 Correct 220 ms 26604 KB Output is correct
3 Correct 190 ms 26736 KB Output is correct
4 Correct 216 ms 26608 KB Output is correct
5 Correct 215 ms 26604 KB Output is correct
6 Correct 197 ms 37096 KB Output is correct
7 Correct 246 ms 30812 KB Output is correct
8 Correct 225 ms 29848 KB Output is correct
9 Correct 229 ms 28728 KB Output is correct
10 Correct 185 ms 21436 KB Output is correct
11 Correct 183 ms 24892 KB Output is correct
12 Correct 182 ms 17040 KB Output is correct
13 Correct 180 ms 15384 KB Output is correct
14 Correct 174 ms 10744 KB Output is correct
15 Correct 159 ms 10236 KB Output is correct
16 Correct 91 ms 8568 KB Output is correct
17 Correct 148 ms 24936 KB Output is correct
18 Correct 129 ms 24928 KB Output is correct
19 Correct 131 ms 25216 KB Output is correct
20 Correct 136 ms 25040 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 26476 KB Output is correct
2 Correct 227 ms 26732 KB Output is correct
3 Incorrect 218 ms 26092 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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