oj.uz

Submission #866174

# Submission time Handle Problem Language Result Execution time Memory
866174 2023-10-25T14:22:49 Z alexander707070 Duathlon (APIO18_duathlon) C++14
31 / 100
 108 ms 31832 KB 
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
 
long long n,m,a[MAXN],b[MAXN];
long long sz[MAXN],szcomp[MAXN],total[MAXN],rem[MAXN];
int comp[MAXN],k;
vector< pair<int,int> > v[MAXN];
vector<int> tree[MAXN];
 
long long ans,sum[MAXN];
 
int dep[MAXN],low[MAXN];
bool li[MAXN],bridge[MAXN];
 
void bcc(int x,int p,int d,int e){
 
    li[x]=true; dep[x]=d; low[x]=dep[x];
 
    for(int i=0;i<v[x].size();i++){
        if(!li[v[x][i].first]){
            bcc(v[x][i].first,x,d+1,v[x][i].second);
            low[x]=min(low[x],low[v[x][i].first]);
        }else if(v[x][i].first!=p){
            low[x]=min(low[x],dep[v[x][i].first]);
        }
    }
 
    if(p!=0 and low[x]==dep[x]){
        bridge[e]=true;
    }
}
 
void dfs(int x,int c){
    li[x]=true; comp[x]=c;
    szcomp[c]++;
 
    for(int i=0;i<v[x].size();i++){
        if(li[v[x][i].first] or bridge[v[x][i].second])continue;
        dfs(v[x][i].first,c);
    }
}
 
void dfs2(int x,int p){
    sz[x]=szcomp[x];

    sum[x]=szcomp[x]*(szcomp[x]-1);
 
    for(int i=0;i<tree[x].size();i++){
        if(tree[x][i]==p)continue;
 
        dfs2(tree[x][i],x);
        sz[x]+=sz[tree[x][i]];
        sum[x]+=sum[tree[x][i]];
    }
}

int root[MAXN];
 
void dfs3(int x,int p,int t,int r){
    total[x]=t; root[x]=r;
 
    for(int i=0;i<tree[x].size();i++){
        if(tree[x][i]==p)continue;
        dfs3(tree[x][i],x,t,r);
    }
}
 
int main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        v[a[i]].push_back({b[i],i});
        v[b[i]].push_back({a[i],i});
    }
 
    for(int i=1;i<=n;i++){
        if(!li[i])bcc(i,0,0,0);
    }
 
    for(int i=1;i<=n;i++)li[i]=false;
 
    for(int i=1;i<=n;i++){
        if(!li[i]){
            k++; dfs(i,k);
        }
    }
 
    for(int i=1;i<=m;i++){
        if(comp[a[i]]==comp[b[i]])continue;
 
        tree[comp[a[i]]].push_back(comp[b[i]]);
        tree[comp[b[i]]].push_back(comp[a[i]]);
    }
 
    for(int i=1;i<=k;i++){
        if(sz[i]==0){
            dfs2(i,0);
            dfs3(i,0,sz[i],i);
        }
    }
 
    for(int i=1;i<=m;i++){
        if(comp[a[i]]==comp[b[i]])continue;
        
        if(sz[comp[a[i]]]<sz[comp[b[i]]])swap(a[i],b[i]);
 
        rem[a[i]]+=sz[comp[b[i]]];
        rem[b[i]]+=total[comp[b[i]]]-sz[comp[b[i]]];
    }
 
    for(int i=1;i<=k;i++){
        ans+=( (total[i])*(total[i]-1) - sum[root[i]] - szcomp[i]*(total[i]-szcomp[i])*2 ) * szcomp[i];
 
        for(int f=0;f<tree[i].size();f++){
            if(sz[tree[i][f]]<sz[i]){
                ans-=(sz[tree[i][f]]*(sz[tree[i][f]]-1) - sum[tree[i][f]] )*szcomp[i];
            }else{
                ans-=( ( (total[i]-sz[i])*(total[i]-sz[i]-1) -  (sum[root[i]] - sum[i]) ) )*szcomp[i];
            }
        }
    }
 
    for(int i=1;i<=n;i++){
        ans+=(szcomp[comp[i]]-1)*(total[comp[i]]-szcomp[comp[i]]-rem[i])*2;
    }
 
    for(int i=1;i<=k;i++){
        ans+=szcomp[i]*(szcomp[i]-1)*(szcomp[i]-2);
    }
 
    cout<<ans<<"\n";
 
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void bcc(int, int, int, int)':
count_triplets.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs3(int, int, int, int)':
count_triplets.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int f=0;f<tree[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Incorrect 3 ms 18780 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 40 ms 30804 KB Output is correct
2 Correct 47 ms 30828 KB Output is correct
3 Correct 50 ms 29144 KB Output is correct
4 Correct 44 ms 30032 KB Output is correct
5 Correct 44 ms 27216 KB Output is correct
6 Correct 52 ms 28228 KB Output is correct
7 Correct 53 ms 27304 KB Output is correct
8 Correct 52 ms 27984 KB Output is correct
9 Correct 48 ms 26548 KB Output is correct
10 Correct 50 ms 26808 KB Output is correct
11 Correct 43 ms 25424 KB Output is correct
12 Correct 39 ms 25296 KB Output is correct
13 Correct 51 ms 25424 KB Output is correct
14 Correct 43 ms 25216 KB Output is correct
15 Correct 45 ms 24920 KB Output is correct
16 Correct 45 ms 24648 KB Output is correct
17 Correct 6 ms 20828 KB Output is correct
18 Correct 6 ms 20828 KB Output is correct
19 Correct 7 ms 20828 KB Output is correct
20 Correct 6 ms 20828 KB Output is correct
21 Correct 6 ms 20824 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 28220 KB Output is correct
2 Correct 56 ms 28244 KB Output is correct
3 Correct 57 ms 28300 KB Output is correct
4 Correct 64 ms 28268 KB Output is correct
5 Correct 58 ms 28296 KB Output is correct
6 Correct 73 ms 31832 KB Output is correct
7 Correct 98 ms 30820 KB Output is correct
8 Correct 108 ms 30056 KB Output is correct
9 Correct 81 ms 29304 KB Output is correct
10 Correct 74 ms 28104 KB Output is correct
11 Correct 69 ms 28456 KB Output is correct
12 Correct 54 ms 28244 KB Output is correct
13 Correct 72 ms 28108 KB Output is correct
14 Correct 62 ms 27668 KB Output is correct
15 Correct 48 ms 27228 KB Output is correct
16 Correct 32 ms 25704 KB Output is correct
17 Correct 53 ms 28608 KB Output is correct
18 Correct 48 ms 28740 KB Output is correct
19 Correct 56 ms 29064 KB Output is correct
20 Correct 44 ms 28736 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 28216 KB Output is correct
2 Correct 83 ms 28124 KB Output is correct
3 Incorrect 61 ms 26796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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