oj.uz

Submission #250468

# Submission time Handle Problem Language Result Execution time Memory
250468 2020-07-18T05:55:35 Z rrrr10000 Duathlon (APIO18_duathlon) C++14
31 / 100
 253 ms 34924 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 ans=0,c,ce;
vi group,gv,ge,lk,ord;
vb used,back_edge;
void dfs(int i,int p,int e){
    group.pb(i);
    used[i]=true;
    for(auto x:g[i]){
        if(x.fi!=p){
            if(ord[x.fi]==-1){
                ord[x.fi]=c++;
                dfs(x.fi,i,x.se);
                chmin(lk[i],lk[x.fi]);
            }
            else{
                chmin(lk[i],ord[x.fi]);
                back_edge[x.se]=true;
            }
        }
    }
}
void dfs1(int i,int p,int e){
    vp dl;
    for(auto x:g[i]){
        if(!back_edge[x.se]&&x.fi!=p){
            if(p!=-1){
                if(lk[x.fi]>=ord[i]){
                    gv[i]=-1;
                    ge[x.se]=ce++;
                    // cout<<i<<' '<<x.se<<' '<<ge[x.se]<<endl;
                }
                else ge[x.se]=ge[e];
                dfs1(x.fi,i,x.se);
            }
            else dl.pb(x);
        }
        else if(x.fi!=p&&ord[x.fi]<ord[i])ge[x.se]=ge[e];
    }
    if(p==-1){
        for(auto x:dl){
            ge[x.se]=ce++;
            dfs1(x.fi,i,x.se);
        }
        if(dl.size()==1)gv[i]=0;
        else gv[i]=-1;
    }
    else if(gv[i]==-2)gv[i]=ge[e];
}
vi f,sz,par;
vvi edge;
ll getsz(int i,int p){
    par[i]=p;
    if(i>=ce)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;cin>>n>>m;
    g=vvp(n);
    used=vb(n,false);
    rep(i,m){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b,i);g[b].pb(a,i);
    }
    lk=vi(n,inf);
    gv=vi(n,-2);
    ge=vi(m);
    back_edge=vb(m,false);
    ord=vi(n,-1);
    rep(i,n){
        if(used[i])continue;
        group=vi(0);
        ord[i]=0;
        c=1;
        ce=0;
        dfs(i,-1,-1);
        if(group.size()<3)continue;
        // outv(lk);outv(ord);
        dfs1(i,-1,-1);
        ll cnt=0;
        // outv(gv);outv(ge);
        f=vi(ce);
        for(ll x:group){
            if(gv[x]==-1)gv[x]=ce+(cnt++);
            else f[gv[x]]++;
        }
        edge=vvi(cnt+ce);
        for(ll x:group){
            if(gv[x]>=ce)for(auto to:g[x]){
                edge[gv[x]].pb(ge[to.se]);
                edge[ge[to.se]].pb(gv[x]);
            }
        }
        rep(j,cnt+ce)dupli(edge[j]);
        // out(ce);out(cnt);
        // out("edge");
        // outvv(edge);
        // outv(f);
        par=vi(ce+cnt);sz=vi(ce+cnt);
        getsz(0,-1);
        vi s(ce);
        rep(i,ce){
            for(ll x:edge[i])if(x!=par[i])s[i]+=sz[x]*(sz[x]-1);
            ans+=f[i]*((group.size()-1)*(group.size()-2)-s[i]);
            if(par[i]!=-1)ans-=f[i]*(group.size()-sz[i])*(group.size()-sz[i]-1);
            // outp(P(i,ans));
        }
        // outv(s);
        REP(i,ce,ce+cnt){
            ans+=(group.size()-1)*(group.size()-2);
            for(ll x:edge[i])if(x!=par[i])ans-=s[x];
            // out(ans);
            ll p=par[i];
            ans-=(s[p]+(group.size()-sz[p])*(group.size()-sz[p]-1)-sz[i]*(sz[i]-1));
            // outp(P(i,ans));
        }
    }
    out(ans);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 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 1 ms 256 KB Output is correct
8 Incorrect 1 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 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 1 ms 256 KB Output is correct
8 Incorrect 1 ms 256 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 168 ms 25984 KB Output is correct
2 Correct 180 ms 26016 KB Output is correct
3 Correct 187 ms 26088 KB Output is correct
4 Correct 181 ms 25832 KB Output is correct
5 Correct 174 ms 20952 KB Output is correct
6 Correct 192 ms 24556 KB Output is correct
7 Correct 211 ms 18056 KB Output is correct
8 Correct 186 ms 20416 KB Output is correct
9 Correct 181 ms 14248 KB Output is correct
10 Correct 239 ms 15648 KB Output is correct
11 Correct 130 ms 10364 KB Output is correct
12 Correct 136 ms 10292 KB Output is correct
13 Correct 120 ms 9848 KB Output is correct
14 Correct 150 ms 9976 KB Output is correct
15 Correct 89 ms 8568 KB Output is correct
16 Correct 90 ms 8604 KB Output is correct
17 Correct 7 ms 4992 KB Output is correct
18 Correct 8 ms 4992 KB Output is correct
19 Correct 7 ms 4992 KB Output is correct
20 Correct 8 ms 4992 KB Output is correct
21 Correct 6 ms 4992 KB Output is correct
22 Correct 7 ms 5120 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 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 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 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 1 ms 512 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 24556 KB Output is correct
2 Correct 206 ms 24620 KB Output is correct
3 Correct 201 ms 24556 KB Output is correct
4 Correct 180 ms 24560 KB Output is correct
5 Correct 179 ms 24556 KB Output is correct
6 Correct 206 ms 34924 KB Output is correct
7 Correct 208 ms 31216 KB Output is correct
8 Correct 198 ms 29548 KB Output is correct
9 Correct 253 ms 27968 KB Output is correct
10 Correct 187 ms 19648 KB Output is correct
11 Correct 219 ms 22892 KB Output is correct
12 Correct 212 ms 15576 KB Output is correct
13 Correct 182 ms 14864 KB Output is correct
14 Correct 172 ms 10488 KB Output is correct
15 Correct 162 ms 9848 KB Output is correct
16 Correct 96 ms 8184 KB Output is correct
17 Correct 127 ms 20840 KB Output is correct
18 Correct 134 ms 20704 KB Output is correct
19 Correct 144 ms 20948 KB Output is correct
20 Correct 149 ms 20812 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 24540 KB Output is correct
2 Correct 242 ms 25068 KB Output is correct
3 Incorrect 229 ms 24684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 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 1 ms 256 KB Output is correct
8 Incorrect 1 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 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 1 ms 256 KB Output is correct
8 Incorrect 1 ms 256 KB Output isn't correct
9 Halted 0 ms 0 KB -