oj.uz

Submission #733675

# Submission time Handle Problem Language Result Execution time Memory
733675 2023-05-01T07:48:13 Z bin9638 Duathlon (APIO18_duathlon) C++17
0 / 100
 131 ms 33604 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)
{
    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);
                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);
   // 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 68 ms 29328 KB Output is correct
2 Correct 78 ms 30576 KB Output is correct
3 Incorrect 97 ms 27172 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 5 ms 9940 KB Output is correct
5 Correct 6 ms 9912 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9812 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 100 ms 24012 KB Output is correct
2 Correct 102 ms 25356 KB Output is correct
3 Correct 104 ms 25292 KB Output is correct
4 Correct 101 ms 25272 KB Output is correct
5 Correct 116 ms 25164 KB Output is correct
6 Correct 108 ms 33604 KB Output is correct
7 Correct 113 ms 30668 KB Output is correct
8 Correct 111 ms 29276 KB Output is correct
9 Correct 106 ms 27852 KB Output is correct
10 Incorrect 88 ms 24828 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 5 ms 9896 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 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 5 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 5 ms 9832 KB Output is correct
12 Correct 6 ms 9868 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 6 ms 9848 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 92 ms 23916 KB Output is correct
2 Correct 100 ms 25068 KB Output is correct
3 Correct 101 ms 24580 KB Output is correct
4 Correct 98 ms 23556 KB Output is correct
5 Correct 101 ms 22504 KB Output is correct
6 Correct 91 ms 21984 KB Output is correct
7 Correct 85 ms 21716 KB Output is correct
8 Correct 80 ms 21488 KB Output is correct
9 Correct 84 ms 21360 KB Output is correct
10 Correct 74 ms 21196 KB Output is correct
11 Correct 81 ms 21160 KB Output is correct
12 Correct 73 ms 21136 KB Output is correct
13 Correct 81 ms 21224 KB Output is correct
14 Correct 67 ms 23364 KB Output is correct
15 Correct 110 ms 30432 KB Output is correct
16 Correct 114 ms 28364 KB Output is correct
17 Correct 110 ms 28876 KB Output is correct
18 Correct 131 ms 27228 KB Output is correct
19 Incorrect 90 ms 23500 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 -