oj.uz

Submission #261631

# Submission time Handle Problem Language Result Execution time Memory
261631 2020-08-11T23:08:30 Z Rouge_Hugo Duathlon (APIO18_duathlon) C++14
23 / 100
 182 ms 30188 KB 
#include<bits/stdc++.h>
#define fi first
#define ll long long
using namespace std;
int n,m;
ll re=0;
int szz=0;
const int N=200009;
vector<pair<int,int>>v[N];
vector<int>v1[N];
ll cnt=1,t[N],num[N],low[N],bridge[N],b[N],par[N],vis[N],sz[N],bo[N];
pair<int,int>a[N];
int tt=0;
void dfs (int x,int p)
{
    vis[x]=1;
    low[x]=num[x]=++tt;
    for(auto it:v[x])
    {
        if (num[it.first]==0)
            dfs(it.first,x);
        if (num[x]<low[it.first])
            bridge[it.second]=1;
        if (it.first!=p)
            low[x]=min(low[x],low[it.first]);
    }
}
void dfs1(int x,int p)
{
    vis[x]=1;
    par[x]=cnt;
    szz++;
    for(auto it:v[x])
    {
        if(it.fi==p)continue;
        if (!vis[it.first]&&bridge[it.second]==0)
        {
            dfs1(it.first,x);
        }
    }
}
void dfs2(int x,int p)
{
    vis[x]=1;
    for(auto it:v[x])
    {
        if(it.fi==p)continue;
        if (!vis[it.first])
            dfs2(it.first,x);
        if (bridge[it.second]==1)
        {
            v1[par[x]].push_back(par[it.first]);
            v1[par[it.first]].push_back(par[x]);
        }
    }
}
void solve(int x,int p)
{
    vis[x]=1;
    for(auto it:v1[x])
    {
        if(it==p)continue;
        solve(it,x);
        sz[x]+=sz[it];
    }
    sz[x]+=bo[x];
}
void go (int x,int p,ll up)
{
    vis[x]=1;
    sz[x]-=bo[x];
    if(bo[x]>=3)
        re+=bo[x]*(bo[x]-1)*(bo[x]-2);
    re+=2*up*bo[x]*sz[x];
    if(bo[x]>2)
    {
        re+=(up)*((bo[x])-1)*((bo[x])-2)*2;
        re+=(sz[x])*(bo[x]-1)*(bo[x]-2)*2;
    }
    re+=(bo[x]-1)*up*2;
    re+=(bo[x]-1)*(sz[x])*2;
    for(auto it:v1[x])
    {
        if(it==p)continue;
        re+=2*t[x]*sz[it];
        t[x]+=sz[it];
        go(it,x,up+bo[x]+sz[x]-sz[it]);
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    scanf("%d %d", &n, &m);
    int x,y;
    for(int i=0; i<m; i++)
    {
        scanf("%d %d", &x, &y);
        a[i]= {x,y};
        v[x].push_back({y,i});
        v[y].push_back({x,i});
    }
    memset (vis,0,sizeof vis);
    for(int i=1;i<n+1;i++)
    {
        if(vis[i])continue;
        dfs(i,-1);
    }
    memset (vis,0,sizeof vis);
    for(int i=1; i<n+1; i++)
    {
        szz=0;
        if (!vis[i])
        {
            szz=0;
            dfs1(i,-1);
            bo[i]=szz;
            cnt++;
        }
    }
    memset (vis,0,sizeof vis);
    for(int i=1;i<n+1;i++)
    {
        if(vis[i])continue;
        dfs2(i,-1);
    }
    memset (vis,0,sizeof vis);
    for(int i=1;i<cnt;i++)
    {
        if(vis[i])continue;
        solve(i,0);
    }
    re=0;
    memset (vis,0,sizeof vis);
    for(int i=1;i<cnt;i++)
    {
        if(vis[i])continue;
        go(i,0,0);
    }
    cout<<re;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11264 KB Output is correct
2 Correct 8 ms 11392 KB Output is correct
3 Correct 7 ms 11400 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 7 ms 11392 KB Output is correct
7 Incorrect 7 ms 11392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11264 KB Output is correct
2 Correct 8 ms 11392 KB Output is correct
3 Correct 7 ms 11400 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 7 ms 11392 KB Output is correct
7 Incorrect 7 ms 11392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 28152 KB Output is correct
2 Correct 119 ms 28280 KB Output is correct
3 Incorrect 128 ms 27512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11520 KB Output is correct
2 Correct 8 ms 11520 KB Output is correct
3 Correct 8 ms 11520 KB Output is correct
4 Correct 8 ms 11520 KB Output is correct
5 Correct 8 ms 11520 KB Output is correct
6 Correct 8 ms 11520 KB Output is correct
7 Correct 9 ms 11520 KB Output is correct
8 Correct 8 ms 11520 KB Output is correct
9 Correct 8 ms 11520 KB Output is correct
10 Correct 8 ms 11520 KB Output is correct
11 Correct 8 ms 11520 KB Output is correct
12 Correct 8 ms 11520 KB Output is correct
13 Correct 8 ms 11520 KB Output is correct
14 Correct 9 ms 11520 KB Output is correct
15 Correct 8 ms 11520 KB Output is correct
16 Correct 7 ms 11392 KB Output is correct
17 Correct 8 ms 11520 KB Output is correct
18 Correct 8 ms 11520 KB Output is correct
19 Correct 10 ms 11520 KB Output is correct
20 Correct 9 ms 11520 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 25848 KB Output is correct
2 Correct 176 ms 25848 KB Output is correct
3 Correct 160 ms 25848 KB Output is correct
4 Correct 162 ms 25848 KB Output is correct
5 Correct 154 ms 25848 KB Output is correct
6 Correct 176 ms 30188 KB Output is correct
7 Correct 176 ms 28920 KB Output is correct
8 Correct 182 ms 28024 KB Output is correct
9 Correct 167 ms 27256 KB Output is correct
10 Correct 150 ms 25848 KB Output is correct
11 Correct 140 ms 25848 KB Output is correct
12 Correct 140 ms 25848 KB Output is correct
13 Correct 137 ms 25848 KB Output is correct
14 Correct 127 ms 25208 KB Output is correct
15 Correct 113 ms 24568 KB Output is correct
16 Correct 82 ms 22136 KB Output is correct
17 Correct 94 ms 25584 KB Output is correct
18 Correct 94 ms 25576 KB Output is correct
19 Correct 115 ms 25688 KB Output is correct
20 Correct 98 ms 25576 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11520 KB Output is correct
2 Correct 8 ms 11520 KB Output is correct
3 Incorrect 10 ms 11520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 25720 KB Output is correct
2 Correct 137 ms 25592 KB Output is correct
3 Incorrect 158 ms 24812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11264 KB Output is correct
2 Correct 8 ms 11392 KB Output is correct
3 Correct 7 ms 11400 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 7 ms 11392 KB Output is correct
7 Incorrect 7 ms 11392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11264 KB Output is correct
2 Correct 8 ms 11392 KB Output is correct
3 Correct 7 ms 11400 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 7 ms 11392 KB Output is correct
7 Incorrect 7 ms 11392 KB Output isn't correct
8 Halted 0 ms 0 KB -