oj.uz

Submission #689363

# Submission time Handle Problem Language Result Execution time Memory
689363 2023-01-28T10:05:46 Z ToroTN Duathlon (APIO18_duathlon) C++14
0 / 100
 109 ms 27956 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
ll n,m,u_i,v_i,dis[100005],low[100005],cnt,bcc,ans=0,num,sz[200005];
vector<ll> v[100005],g[200005];
stack<ll> stk;
void dfs(ll u,ll p)
{
    dis[u]=low[u]=++cnt;
    ++num;
    stk.push(u);
    for(auto node:v[u])
    {
        if(node==p)continue;
        if(dis[node]!=0)
        {
            low[u]=min(low[u],dis[node]);
        }else
        {
            dfs(node,u);
            low[u]=min(low[u],low[node]);
            if(dis[u]<=low[node])
            {
                ++bcc;
                //printf("node=%d\n",node);
                g[u].pb(n+bcc);
                while(!g[n+bcc].size()||g[n+bcc].back()!=node)
                {
                    g[n+bcc].pb(stk.top());
                    stk.pop();
                }
            }
        }
    }
}
void dfs2(ll u)
{
    sz[u]=(u<=n);
    for(auto node:g[u])
    {
        dfs2(node);
        sz[u]+=sz[node];
        if(u>n)ans-=(ll)g[u].size()*sz[node]*(sz[node]-1);
    }
    if(u>n)ans-=(ll)g[u].size()*(n-sz[u])*(n-sz[u]-1);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&u_i,&v_i);
        v[u_i].pb(v_i);
        v[v_i].pb(u_i);
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0)
        {
            num=0;
            dfs(i,0);
            ans+=num*(num-1)*(num-2);
            dfs2(i);
        }
    }
    /*for(int i=1;i<=6;i++)
    {
        printf("i=%d\n",i);
        for(auto node:g[i])
        {
            printf("%lld ",node);
        }
        printf("\n");
    }
    for(int i=1;i<=6;i++)
    {
        printf("%lld ",sz[i]);
    }
    printf("\n");*/
    printf("%lld\n",ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%lld%lld",&u_i,&v_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 25140 KB Output is correct
2 Correct 68 ms 25128 KB Output is correct
3 Incorrect 78 ms 23152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7492 KB Output is correct
5 Correct 6 ms 7508 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7492 KB Output is correct
9 Correct 4 ms 7492 KB Output is correct
10 Incorrect 5 ms 7380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 20564 KB Output is correct
2 Correct 76 ms 20432 KB Output is correct
3 Correct 79 ms 20364 KB Output is correct
4 Correct 81 ms 20444 KB Output is correct
5 Correct 77 ms 20408 KB Output is correct
6 Correct 89 ms 27956 KB Output is correct
7 Correct 109 ms 25288 KB Output is correct
8 Correct 94 ms 24004 KB Output is correct
9 Correct 83 ms 22784 KB Output is correct
10 Incorrect 77 ms 20340 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 7492 KB Output is correct
2 Correct 5 ms 7496 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7392 KB Output is correct
11 Correct 6 ms 7448 KB Output is correct
12 Correct 5 ms 7508 KB Output is correct
13 Correct 4 ms 7488 KB Output is correct
14 Correct 4 ms 7508 KB Output is correct
15 Correct 4 ms 7492 KB Output is correct
16 Incorrect 4 ms 7380 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20380 KB Output is correct
2 Correct 79 ms 20552 KB Output is correct
3 Correct 90 ms 20016 KB Output is correct
4 Correct 90 ms 18892 KB Output is correct
5 Correct 74 ms 17428 KB Output is correct
6 Correct 68 ms 16964 KB Output is correct
7 Correct 70 ms 16572 KB Output is correct
8 Correct 58 ms 15964 KB Output is correct
9 Correct 65 ms 15856 KB Output is correct
10 Correct 58 ms 15680 KB Output is correct
11 Correct 61 ms 15556 KB Output is correct
12 Correct 59 ms 15416 KB Output is correct
13 Correct 61 ms 15600 KB Output is correct
14 Correct 55 ms 17892 KB Output is correct
15 Correct 100 ms 24956 KB Output is correct
16 Correct 89 ms 23284 KB Output is correct
17 Correct 90 ms 23708 KB Output is correct
18 Correct 93 ms 22256 KB Output is correct
19 Incorrect 80 ms 18872 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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