oj.uz

Submission #733662

# Submission time Handle Problem Language Result Execution time Memory
733662 2023-05-01T07:24:06 Z bin9638 Duathlon (APIO18_duathlon) C++17
0 / 100
 145 ms 32304 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

ll ans=0;
ll 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(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);
                          //  cout<<k<<" "<<dem<<endl;
                        }
                    }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)
    {
        ll sum=n-1;
        for(auto v:edge[u])
            if(v!=p)
            {
                sum-=child[v];
                ans+=1ll*sum*child[v];
             //   cout<<sum<<" "<<child[v]<<endl;
            }
    }else
    {
        ll sum=n;
        for(auto v:edge[u])
            if(v!=p)
            {
                sum-=child[v];
                ans+=1ll*sum*child[v]*(sz[u]-2);
            //   cout<<u<<" "<<sum<<" "<<child[v]<<" "<<sz[u]-2<<" "<<sum*child[v]*(sz[u]-2)<<endl;
               // cout<<u<<" "<<sum<<" "<<child[v]<<" "<<sz[u]<<endl;
            }
    }
    //cout<<u<<" "<<ans*2<<endl;
    for(auto v:edge[u])
        if(v!=p)
            DFS(v,u);
}

int main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    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 Correct 72 ms 29304 KB Output is correct
2 Correct 87 ms 29328 KB Output is correct
3 Incorrect 114 ms 25928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 8 ms 10008 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9948 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 5 ms 9844 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 Correct 123 ms 23948 KB Output is correct
2 Correct 112 ms 23920 KB Output is correct
3 Correct 88 ms 24020 KB Output is correct
4 Correct 90 ms 23944 KB Output is correct
5 Correct 105 ms 24012 KB Output is correct
6 Correct 123 ms 32304 KB Output is correct
7 Correct 114 ms 29404 KB Output is correct
8 Correct 105 ms 28064 KB Output is correct
9 Correct 104 ms 26572 KB Output is correct
10 Incorrect 96 ms 23652 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 7 ms 9812 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 5 ms 9812 KB Output is correct
12 Correct 6 ms 9940 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Incorrect 6 ms 9812 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 24012 KB Output is correct
2 Correct 112 ms 23932 KB Output is correct
3 Correct 98 ms 23084 KB Output is correct
4 Correct 93 ms 22000 KB Output is correct
5 Correct 87 ms 21120 KB Output is correct
6 Correct 98 ms 20560 KB Output is correct
7 Correct 99 ms 20480 KB Output is correct
8 Correct 73 ms 20072 KB Output is correct
9 Correct 77 ms 20172 KB Output is correct
10 Correct 95 ms 20012 KB Output is correct
11 Correct 96 ms 19916 KB Output is correct
12 Correct 68 ms 19916 KB Output is correct
13 Correct 76 ms 20012 KB Output is correct
14 Correct 83 ms 22060 KB Output is correct
15 Correct 145 ms 29124 KB Output is correct
16 Correct 101 ms 26960 KB Output is correct
17 Correct 99 ms 27432 KB Output is correct
18 Correct 114 ms 25720 KB Output is correct
19 Incorrect 111 ms 21960 KB Output isn't correct
20 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 -