oj.uz

Submission #262099

# Submission time Handle Problem Language Result Execution time Memory
262099 2020-08-12T10:52:31 Z Rouge_Hugo Duathlon (APIO18_duathlon) C++14
31 / 100
 167 ms 30320 KB 
#include<bits/stdc++.h>
#define fi first
#define ll long long
#define pb push_back
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;
vector<int>nd;
void dfs (int x,int p)
{
    nd.pb(x);
    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]);
    }
        if(low[x] == num[x]) {
            int w=1;
        while(nd.back() != x) {
            par[nd.back()] = cnt;
            nd.pop_back();w++;
        }
        par[nd.back()] = cnt;
        nd.pop_back();
        bo[cnt]=w;
        cnt++;
    }
}
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];
    re+=(up)*((bo[x])-1)*((bo[x])-1)*2;
    re+=(sz[x])*(bo[x]-1)*(bo[x]-1)*2;
    for(auto it:v1[x])
    {
        if(it==p)continue;
        re+=2*t[x]*sz[it]*bo[x];
        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++)
    {
        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:88: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:92: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 11392 KB Output is correct
2 Correct 7 ms 11392 KB Output is correct
3 Correct 8 ms 11392 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 9 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 11392 KB Output is correct
2 Correct 7 ms 11392 KB Output is correct
3 Correct 8 ms 11392 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 9 ms 11392 KB Output is correct
7 Incorrect 7 ms 11392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 27512 KB Output is correct
2 Correct 112 ms 27508 KB Output is correct
3 Correct 130 ms 25984 KB Output is correct
4 Correct 141 ms 28512 KB Output is correct
5 Correct 129 ms 24692 KB Output is correct
6 Correct 126 ms 26228 KB Output is correct
7 Correct 116 ms 24824 KB Output is correct
8 Correct 126 ms 25720 KB Output is correct
9 Correct 118 ms 23928 KB Output is correct
10 Correct 112 ms 24252 KB Output is correct
11 Correct 119 ms 22264 KB Output is correct
12 Correct 98 ms 22264 KB Output is correct
13 Correct 91 ms 22264 KB Output is correct
14 Correct 83 ms 22008 KB Output is correct
15 Correct 69 ms 21624 KB Output is correct
16 Correct 71 ms 21368 KB Output is correct
17 Correct 13 ms 15744 KB Output is correct
18 Correct 13 ms 15744 KB Output is correct
19 Correct 13 ms 15616 KB Output is correct
20 Correct 13 ms 15616 KB Output is correct
21 Correct 15 ms 15616 KB Output is correct
22 Correct 14 ms 15488 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 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 8 ms 11520 KB Output is correct
8 Correct 8 ms 11520 KB Output is correct
9 Correct 9 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 8 ms 11520 KB Output is correct
15 Correct 8 ms 11520 KB Output is correct
16 Correct 8 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 8 ms 11520 KB Output is correct
20 Correct 8 ms 11520 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 24544 KB Output is correct
2 Correct 121 ms 24592 KB Output is correct
3 Correct 123 ms 24568 KB Output is correct
4 Correct 128 ms 24568 KB Output is correct
5 Correct 121 ms 24600 KB Output is correct
6 Correct 137 ms 30320 KB Output is correct
7 Correct 167 ms 27764 KB Output is correct
8 Correct 147 ms 27116 KB Output is correct
9 Correct 143 ms 26020 KB Output is correct
10 Correct 138 ms 24568 KB Output is correct
11 Correct 136 ms 24568 KB Output is correct
12 Correct 130 ms 24568 KB Output is correct
13 Correct 137 ms 24568 KB Output is correct
14 Correct 134 ms 24056 KB Output is correct
15 Correct 106 ms 23548 KB Output is correct
16 Correct 80 ms 21624 KB Output is correct
17 Correct 71 ms 24296 KB Output is correct
18 Correct 72 ms 24292 KB Output is correct
19 Correct 76 ms 24552 KB Output is correct
20 Correct 76 ms 24492 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 8 ms 11392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 24568 KB Output is correct
2 Correct 124 ms 24568 KB Output is correct
3 Incorrect 136 ms 23160 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 11392 KB Output is correct
2 Correct 7 ms 11392 KB Output is correct
3 Correct 8 ms 11392 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 9 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 11392 KB Output is correct
2 Correct 7 ms 11392 KB Output is correct
3 Correct 8 ms 11392 KB Output is correct
4 Correct 7 ms 11392 KB Output is correct
5 Correct 7 ms 11392 KB Output is correct
6 Correct 9 ms 11392 KB Output is correct
7 Incorrect 7 ms 11392 KB Output isn't correct
8 Halted 0 ms 0 KB -