oj.uz

Submission #866184

# Submission time Handle Problem Language Result Execution time Memory
866184 2023-10-25T14:39:15 Z alexander707070 Duathlon (APIO18_duathlon) C++14
31 / 100
 80 ms 33620 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);
    }
}

int num[MAXN],w,last[MAXN];

void dfs2(int x,int p){
    sz[x]=szcomp[x];

    w++; num[x]=w;

    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]];
    }

    last[x]=w;
}

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);
    }
}

bool check(int x,int y){
    return num[y]>=num[x] and num[y]<=last[x];
}
 
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]]]-szcomp[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:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs3(int, int, int, int)':
count_triplets.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int f=0;f<tree[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20828 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20824 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 3 ms 21080 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 20828 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20824 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 3 ms 21080 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 32812 KB Output is correct
2 Correct 40 ms 32596 KB Output is correct
3 Correct 49 ms 31064 KB Output is correct
4 Correct 46 ms 31824 KB Output is correct
5 Correct 44 ms 29016 KB Output is correct
6 Correct 48 ms 30080 KB Output is correct
7 Correct 53 ms 29008 KB Output is correct
8 Correct 49 ms 29840 KB Output is correct
9 Correct 52 ms 28432 KB Output is correct
10 Correct 64 ms 28644 KB Output is correct
11 Correct 44 ms 27220 KB Output is correct
12 Correct 42 ms 27272 KB Output is correct
13 Correct 50 ms 27476 KB Output is correct
14 Correct 40 ms 27184 KB Output is correct
15 Correct 33 ms 27228 KB Output is correct
16 Correct 33 ms 26968 KB Output is correct
17 Correct 7 ms 22876 KB Output is correct
18 Correct 7 ms 22876 KB Output is correct
19 Correct 6 ms 22876 KB Output is correct
20 Correct 6 ms 22896 KB Output is correct
21 Correct 6 ms 22876 KB Output is correct
22 Correct 6 ms 23012 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 30116 KB Output is correct
2 Correct 80 ms 29916 KB Output is correct
3 Correct 76 ms 30036 KB Output is correct
4 Correct 55 ms 30036 KB Output is correct
5 Correct 55 ms 30036 KB Output is correct
6 Correct 62 ms 33620 KB Output is correct
7 Correct 68 ms 32604 KB Output is correct
8 Correct 65 ms 31932 KB Output is correct
9 Correct 60 ms 31196 KB Output is correct
10 Correct 56 ms 29912 KB Output is correct
11 Correct 54 ms 30032 KB Output is correct
12 Correct 57 ms 30148 KB Output is correct
13 Correct 55 ms 30032 KB Output is correct
14 Correct 73 ms 29792 KB Output is correct
15 Correct 46 ms 29436 KB Output is correct
16 Correct 37 ms 27652 KB Output is correct
17 Correct 45 ms 30404 KB Output is correct
18 Correct 50 ms 30608 KB Output is correct
19 Correct 48 ms 30912 KB Output is correct
20 Correct 48 ms 30532 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 29992 KB Output is correct
2 Correct 60 ms 29776 KB Output is correct
3 Incorrect 60 ms 28616 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 20828 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20824 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 3 ms 21080 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 20828 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20824 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 3 ms 21080 KB Output isn't correct
8 Halted 0 ms 0 KB -