oj.uz

Submission #754225

# Submission time Handle Problem Language Result Execution time Memory
754225 2023-06-07T09:22:57 Z bgnbvnbv Duathlon (APIO18_duathlon) C++14
0 / 100
 129 ms 44216 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
stack< int > stt;
bool minimize(int &a, int b){ if (a>b) a=b; else return false; return true; }
bool maximize(int &a, int b){ if (a<b) a=b; else return false; return true; }
ll low[maxN],num[maxN],Time=0;
vector<ll>g[maxN];
ll cnt=0;
int lc[maxN];
vector<ll> ver;
vector<ll>bcc[maxN];
bool vis[maxN];
void DFS(int u){
   ver.pb(u);
   low[u]=num[u]=++Time;
   for (auto v:g[u]){
      if (num[v]) low[u]=min(low[u], num[v]);
      else {
         stt.push(u);
         DFS(v);
        low[u]=min(low[u], low[v]);
         if (low[v]>=num[u]) {
            cnt++;
            do {
               v=stt.top(); stt.pop();
               if (maximize(lc[v], cnt)==true) bcc[cnt].pb(v);
            } while (u!=v);
         }
      }
   }
   stt.push(u);
}
ll n,m,u,v;
ll ct[maxN],val[maxN],ans=0,vc=0;
vector<ll>adj[maxN];

void dfs(ll u,ll p)
{
    ct[u]=val[u];
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            dfs(v,u);
            ct[u]+=ct[v];
        }
    }
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            vc+=ct[v]*val[u]*(ct[u]-ct[v]-val[u]);
        }
    }
    vc+=(ct[u]-val[u])*val[u]*(ver.size()-ct[u]);
}
ll val2[maxN];
vector<ll>vec[maxN];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int dm=1;dm<=n;dm++)
    {
        if(num[dm]>0) continue;
        ver.clear();
        for(int i=1;i<=cnt;i++) adj[i].clear(),bcc[i].clear();
        cnt=0;
        DFS(dm);
        for(int i=1;i<=cnt;i++)
        {
            for(auto zz:bcc[i])
            {
                vec[zz].pb(i);
            }
            if(bcc[i].size()>=3)
            {
                ll x=bcc[i].size();
                ans+=x*(x-1)*(x-2);
            }
            val[i]=bcc[i].size();
        }
        for(auto i:ver)
        {
            if(vec[i].size()==1) continue;
            cnt++;
            for(auto zz:vec[i])
            {
                adj[cnt].pb(zz);
                adj[zz].pb(cnt);
                val[zz]--;
            }
            val[cnt]++;
        }
        ll sum=0;
        for(int i=1;i<=cnt;i++)
        {
            val2[i]=val[i]*(val[i]-1);
            sum+=val2[i];
        }
        dfs(1,1);
        vc*=2;
        ans+=vc;
        //cout << ans << '\n';
        for(int i=1;i<=cnt;i++)
        {
            vc=sum-val2[i];
            for(auto j:adj[i])
            {
                vc-=val2[j];
            }
            ans+=vc*val[i];
            vc=ver.size()-val[i];
            for(auto j:adj[i])
            {
                vc-=val[j];
            }
            ans+=vc*val2[i];
        }
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 39380 KB Output is correct
2 Correct 89 ms 39396 KB Output is correct
3 Correct 108 ms 44216 KB Output is correct
4 Incorrect 85 ms 40348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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