oj.uz

Submission #733655

# Submission time Handle Problem Language Result Execution time Memory
733655 2023-05-01T07:16:15 Z bin9638 Duathlon (APIO18_duathlon) C++17
0 / 100
 123 ms 32356 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(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)
    {
        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]<<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 74 ms 29392 KB Output is correct
2 Correct 71 ms 29300 KB Output is correct
3 Incorrect 76 ms 25912 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 5 ms 9812 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 6 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 5 ms 9812 KB Output is correct
10 Incorrect 7 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 92 ms 23932 KB Output is correct
2 Correct 95 ms 24016 KB Output is correct
3 Correct 91 ms 23960 KB Output is correct
4 Correct 92 ms 23944 KB Output is correct
5 Correct 100 ms 23924 KB Output is correct
6 Correct 100 ms 32356 KB Output is correct
7 Correct 105 ms 29512 KB Output is correct
8 Correct 123 ms 28012 KB Output is correct
9 Correct 102 ms 26564 KB Output is correct
10 Incorrect 88 ms 23624 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 9880 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 6 ms 9952 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Incorrect 5 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 91 ms 24092 KB Output is correct
2 Correct 100 ms 23840 KB Output is correct
3 Correct 99 ms 23040 KB Output is correct
4 Correct 95 ms 22088 KB Output is correct
5 Correct 87 ms 20984 KB Output is correct
6 Correct 80 ms 20604 KB Output is correct
7 Correct 75 ms 20320 KB Output is correct
8 Correct 82 ms 20348 KB Output is correct
9 Correct 69 ms 20036 KB Output is correct
10 Correct 74 ms 19916 KB Output is correct
11 Correct 72 ms 19828 KB Output is correct
12 Correct 80 ms 19960 KB Output is correct
13 Correct 70 ms 20008 KB Output is correct
14 Correct 88 ms 22204 KB Output is correct
15 Correct 102 ms 28984 KB Output is correct
16 Correct 107 ms 26936 KB Output is correct
17 Correct 100 ms 27468 KB Output is correct
18 Correct 108 ms 25676 KB Output is correct
19 Incorrect 119 ms 22012 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 -