oj.uz

Submission #754218

# Submission time Handle Problem Language Result Execution time Memory
754218 2023-06-07T09:14:12 Z bgnbvnbv Duathlon (APIO18_duathlon) C++14
0 / 100
 153 ms 41716 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>bcc[maxN];
void DFS(int 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]*(n-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);
    }
    DFS(1);
    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(int i=1;i<=n;i++)
    {
        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=n-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 19156 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 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 38788 KB Output is correct
2 Correct 78 ms 38708 KB Output is correct
3 Incorrect 68 ms 32896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 41660 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 19156 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 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -