oj.uz

Submission #1087819

# Submission time Handle Problem Language Result Execution time Memory
1087819 2024-09-13T09:15:16 Z alexander707070 Duathlon (APIO18_duathlon) C++14
66 / 100
 67 ms 26708 KB 
#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

long long n,m,a[MAXN],b[MAXN],k;

vector< pair<int,int> > v[MAXN];
vector<int> tree[MAXN];

long long sz[MAXN],sum[MAXN],szcomp[MAXN],ans;

bool li[MAXN],bridge[MAXN];
int dp[MAXN],low[MAXN];

long long comp[MAXN],where[MAXN];

void bcc(int x,int p,int dep,int edge){
    li[x]=true; dp[x]=low[x]=dep;

    for(int i=0;i<v[x].size();i++){
        if(!li[v[x][i].first]){
            bcc(v[x][i].first,x,dep+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],dp[v[x][i].first]);
        }
    }

    if(p!=0 and low[x]==dp[x]){
        bridge[edge]=true;
    }
}

void mark(int x){
    comp[k]++;
    where[x]=k;
    li[x]=true;

    for(int i=0;i<v[x].size();i++){
        if(li[v[x][i].first] or bridge[v[x][i].second])continue;
        mark(v[x][i].first);
    }
}

void dfs(int x,int p){
    sz[x]=comp[x];

    for(int i=0;i<tree[x].size();i++){
        if(tree[x][i]==p or sz[tree[x][i]]!=0)continue;
        dfs(tree[x][i],x);

        sum[x]+=sz[tree[x][i]]*(sz[tree[x][i]]-1);
        sz[x]+=sz[tree[x][i]];
    }
}

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

    for(int i=0;i<tree[x].size();i++){
        if(tree[x][i]==p or szcomp[tree[x][i]]!=0)continue;
        dfs2(tree[x][i],x,s);
    }

    sum[x]+=(s-sz[x])*(s-sz[x]-1);
}

bool check(int x,int y,int z,bool s){
    if(x==y)s=true;

    if(x==z and s)return true;

    for(int i=0;i<v[x].size();i++){
        if(!li[v[x][i].first]){
            li[v[x][i].first]=true;
            if(check(v[x][i].first,y,z,s))return true;
            li[v[x][i].first]=false;
        }
    }

    return false;
}

void brute(){
    int res=0;
    for(int i=1;i<=n;i++){
        for(int f=1;f<=n;f++){
            for(int t=1;t<=n;t++){
                if(i==f or f==t or i==t)continue;

                for(int z=1;z<=n;z++)li[z]=false;
                li[i]=true;
                if(check(i,f,t,false))res++;
            }
        }
    }

    cout<<res<<"\n";
}

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++; mark(i);
        }
    }

    for(int i=1;i<=m;i++){
        if(where[a[i]]==where[b[i]])continue;

        tree[where[a[i]]].push_back(where[b[i]]);
        tree[where[b[i]]].push_back(where[a[i]]);
    }

    for(int i=1;i<=k;i++){
        if(sz[i]==0){
            dfs(i,0);
            dfs2(i,0,sz[i]);
        }
    }

    for(int i=1;i<=k;i++){
        ans+=(long long) comp[i]*((szcomp[i]-1)*(szcomp[i]-2)-sum[i]);
        ans-=(long long) 2*(comp[i]-1)*(szcomp[i]-comp[i]);
    }

    for(int i=1;i<=n;i++){
        long long res=0,sq=0;

        for(int f=0;f<v[i].size();f++){
            if(where[i]==where[v[i][f].first])continue;
            
            if(sz[where[i]]>sz[where[v[i][f].first]]){
                res+=sz[where[v[i][f].first]];
                sq+=(sz[where[v[i][f].first]]-1)*sz[where[v[i][f].first]];
            }else{
                res+=(szcomp[where[i]]-sz[where[i]]);
                sq+=(szcomp[where[i]]-sz[where[i]])*(szcomp[where[i]]-sz[where[i]]-1);
            }
        }

        res=res*(res-1);
        res-=sq;

        ans-=(long long) (comp[where[i]]-1)*res;
    }

    cout<<ans<<"\n";

    return 0;
}

/**
 19 24
1 2
2 3
3 4
4 1
5 6
6 7
7 5
8 9
9 10
10 8
11 12
12 13
13 11
14 15
15 16
16 14
17 18
18 19
17 19
7 8
4 5
7 11
13 17
12 14
 */

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 mark(int)':
count_triplets.cpp:39: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]
   39 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int, int)':
count_triplets.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'bool check(int, int, int, bool)':
count_triplets.cpp:73: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]
   73 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24032 KB Output is correct
2 Correct 44 ms 23888 KB Output is correct
3 Correct 56 ms 23376 KB Output is correct
4 Correct 48 ms 23644 KB Output is correct
5 Correct 47 ms 20820 KB Output is correct
6 Correct 56 ms 22272 KB Output is correct
7 Correct 55 ms 21588 KB Output is correct
8 Correct 54 ms 22096 KB Output is correct
9 Correct 56 ms 20820 KB Output is correct
10 Correct 59 ms 20820 KB Output is correct
11 Correct 51 ms 19536 KB Output is correct
12 Correct 41 ms 19540 KB Output is correct
13 Correct 43 ms 19796 KB Output is correct
14 Correct 41 ms 19540 KB Output is correct
15 Correct 33 ms 19292 KB Output is correct
16 Correct 34 ms 19032 KB Output is correct
17 Correct 8 ms 14684 KB Output is correct
18 Correct 8 ms 14684 KB Output is correct
19 Correct 7 ms 14684 KB Output is correct
20 Correct 7 ms 14684 KB Output is correct
21 Correct 7 ms 14684 KB Output is correct
22 Correct 7 ms 14516 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 5 ms 10076 KB Output is correct
6 Correct 5 ms 10076 KB Output is correct
7 Correct 4 ms 10076 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 4 ms 9816 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 10048 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 5 ms 10052 KB Output is correct
15 Correct 4 ms 9852 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 4 ms 9820 KB Output is correct
18 Correct 5 ms 9992 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 23124 KB Output is correct
2 Correct 58 ms 23304 KB Output is correct
3 Correct 57 ms 23116 KB Output is correct
4 Correct 59 ms 23160 KB Output is correct
5 Correct 62 ms 23120 KB Output is correct
6 Correct 67 ms 26708 KB Output is correct
7 Correct 65 ms 25640 KB Output is correct
8 Correct 65 ms 24916 KB Output is correct
9 Correct 62 ms 24436 KB Output is correct
10 Correct 60 ms 23116 KB Output is correct
11 Correct 56 ms 23120 KB Output is correct
12 Correct 57 ms 23120 KB Output is correct
13 Correct 56 ms 23120 KB Output is correct
14 Correct 51 ms 22836 KB Output is correct
15 Correct 48 ms 22096 KB Output is correct
16 Correct 31 ms 20056 KB Output is correct
17 Correct 40 ms 23748 KB Output is correct
18 Correct 43 ms 23620 KB Output is correct
19 Correct 48 ms 24004 KB Output is correct
20 Correct 45 ms 23620 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 5 ms 9760 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 10064 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 4 ms 9820 KB Output is correct
18 Correct 4 ms 9796 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Correct 4 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 4 ms 9928 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 5 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 6 ms 9820 KB Output is correct
27 Correct 5 ms 9928 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 23120 KB Output is correct
2 Correct 64 ms 23128 KB Output is correct
3 Correct 57 ms 21336 KB Output is correct
4 Correct 53 ms 21384 KB Output is correct
5 Correct 50 ms 19792 KB Output is correct
6 Correct 48 ms 19024 KB Output is correct
7 Correct 45 ms 18516 KB Output is correct
8 Correct 42 ms 18372 KB Output is correct
9 Correct 41 ms 18004 KB Output is correct
10 Correct 45 ms 18004 KB Output is correct
11 Correct 42 ms 18000 KB Output is correct
12 Correct 40 ms 17784 KB Output is correct
13 Correct 45 ms 17904 KB Output is correct
14 Correct 40 ms 19544 KB Output is correct
15 Correct 64 ms 25940 KB Output is correct
16 Correct 66 ms 24916 KB Output is correct
17 Correct 66 ms 24984 KB Output is correct
18 Correct 57 ms 23832 KB Output is correct
19 Correct 54 ms 21176 KB Output is correct
20 Correct 54 ms 21264 KB Output is correct
21 Correct 53 ms 21252 KB Output is correct
22 Correct 49 ms 20568 KB Output is correct
23 Correct 45 ms 19796 KB Output is correct
24 Correct 51 ms 23108 KB Output is correct
25 Correct 55 ms 23268 KB Output is correct
26 Correct 60 ms 21964 KB Output is correct
27 Correct 54 ms 22100 KB Output is correct

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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