oj.uz

Submission #733624

# Submission time Handle Problem Language Result Execution time Memory
733624 2023-05-01T05:15:29 Z bin9638 Duathlon (APIO18_duathlon) C++17
0 / 100
 96 ms 28952 KB 
#include <bits/stdc++.h>

using namespace std;

#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int ans=0,times,num[N],low[N],n,m,ktr[N],dem,sz[N],child[N];
vector<int>g[N],edge[N];
stack<int>st;

void visit(int u,int p)
{
    num[u]=low[u]=++times;
    for(auto v:g[u])
        if(v!=p)
        {
            if(num[v]!=0)
            {
                low[u]=min(low[u],num[v]);
            }else
            {
                st.push(u);
                visit(v,u);
                low[u]=min(low[u],low[v]);
                if(low[v]>=num[u])
                {
                    int k;
                    dem++;
                    do{
                        k=st.top();
                        st.pop();

                        if(ktr[k]!=dem)
                        {
                             sz[dem]++;
                            ktr[k]=dem;
                            edge[dem].pb(k);
                            edge[k].pb(dem);
                        }
                    }while(k!=u);
                }
            }
        }
    st.push(u);
}

void build(int u,int p)
{
    child[u]=(u<=n);
    //cout<<u<<" "<<child[u]<<endl;
    for(auto v:edge[u])
        if(v!=p)
        {
            build(v,u);
            child[u]+=child[v];
        }
}

void DFS(int u,int p)
{
    if(u<=n)
    {
        int sum=n-1;
        for(auto v:edge[u])
            if(v!=p)
            {
                sum-=child[v];
                ans+=sum*child[v];
            //    cout<<sum<<" "<<child[v]<<endl;
            }
    }else
    {
        int sum=n;
        for(auto v:edge[u])
            if(v!=p)
            {
                sum-=child[v];
                ans+=sum*child[v]*(sz[u]-2);
               // cout<<u<<" "<<sum<<" "<<child[v]<<" "<<sz[u]<<endl;
            }
    }
    //cout<<u<<" "<<ans*2<<endl;
    for(auto v:edge[u])
        if(v!=p)
            DFS(v,u);
}

int32_t main()
{
  //  freopen("A.inp","r",stdin);
  //  freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dem=n;
    for(int i=1;i<=n;i++)
        if(num[i]==0)
            visit(i,0);
    //cout<<dem<<endl;
    build(1,0);
  // cout<<child[1]<<endl;
    DFS(1,0);
    cout<<ans*2;
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9864 KB Output is correct
4 Correct 6 ms 9988 KB Output is correct
5 Correct 6 ms 9868 KB Output is correct
6 Correct 6 ms 9848 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9872 KB Output is correct
9 Correct 6 ms 9860 KB Output is correct
10 Incorrect 6 ms 9812 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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