oj.uz

Submission #1087881

# Submission time Handle Problem Language Result Execution time Memory
1087881 2024-09-13T10:50:28 Z alexander707070 Duathlon (APIO18_duathlon) C++14
71 / 100
 691 ms 27616 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);
}

deque<int> q;
bool vis[MAXN];
int par[MAXN];

void dobfs(int x){
    for(int i=1;i<=n;i++)li[i]=false;

    for(int i=1;i<=n;i++){
        random_shuffle(v[i].begin(),v[i].end());
    }

    q.push_back(x); par[x]=0;
    li[x]=true;

    while(!q.empty()){
        int curr;
        if(rand()%10<7){
            curr=q.front(); q.pop_front();
        }else{
            curr=q.back(); q.pop_back();
        }

        for(int i=0;i<v[curr].size();i++){
            if(li[v[curr][i].first] or vis[v[curr][i].first])continue;

            q.push_back(v[curr][i].first);
            li[v[curr][i].first]=true;
            par[v[curr][i].first]=curr;
        }
    }    
}

bool check(int x,int y,int z){
    for(int i=1;i<=n;i++)vis[i]=false;

    dobfs(x);

    if(!li[y])return false;

    int w=y;
    while(y!=x){
        y=par[y];
        vis[y]=true;
    }

    if(vis[z])return false;

    dobfs(z);

    return li[w];
}

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 or i>t)continue;

                for(int test=1;test<=3;test++){
                    if(check(i,f,t) or check(t,f,i)){
                        res+=2; break;
                    }
                }
            }
        }
    }

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

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

    if(n<=50){
        brute();
        return 0;
    }

    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 'void dobfs(int)':
count_triplets.cpp:90: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]
   90 |         for(int i=0;i<v[curr].size();i++){
      |                     ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:193: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]
  193 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9816 KB Output is correct
5 Correct 4 ms 9880 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9880 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9732 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 4 ms 9876 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 7 ms 9820 KB Output is correct
24 Correct 5 ms 9796 KB Output is correct
25 Correct 5 ms 9820 KB Output is correct
26 Correct 5 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9820 KB Output is correct
29 Correct 5 ms 9800 KB Output is correct
30 Correct 7 ms 10072 KB Output is correct
31 Correct 4 ms 9816 KB Output is correct
32 Correct 5 ms 9820 KB Output is correct
33 Correct 4 ms 9816 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 5 ms 9820 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9816 KB Output is correct
5 Correct 4 ms 9880 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9880 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9732 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 4 ms 9876 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 7 ms 9820 KB Output is correct
24 Correct 5 ms 9796 KB Output is correct
25 Correct 5 ms 9820 KB Output is correct
26 Correct 5 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9820 KB Output is correct
29 Correct 5 ms 9800 KB Output is correct
30 Correct 7 ms 10072 KB Output is correct
31 Correct 4 ms 9816 KB Output is correct
32 Correct 5 ms 9820 KB Output is correct
33 Correct 4 ms 9816 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 5 ms 9820 KB Output is correct
36 Correct 30 ms 9816 KB Output is correct
37 Correct 127 ms 9816 KB Output is correct
38 Incorrect 691 ms 9816 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 23908 KB Output is correct
2 Correct 40 ms 23892 KB Output is correct
3 Correct 55 ms 23380 KB Output is correct
4 Correct 48 ms 23684 KB Output is correct
5 Correct 47 ms 21588 KB Output is correct
6 Correct 58 ms 23060 KB Output is correct
7 Correct 52 ms 22228 KB Output is correct
8 Correct 56 ms 23060 KB Output is correct
9 Correct 72 ms 21588 KB Output is correct
10 Correct 51 ms 21636 KB Output is correct
11 Correct 42 ms 20304 KB Output is correct
12 Correct 46 ms 20284 KB Output is correct
13 Correct 55 ms 20368 KB Output is correct
14 Correct 37 ms 20112 KB Output is correct
15 Correct 31 ms 19988 KB Output is correct
16 Correct 32 ms 19548 KB Output is correct
17 Correct 8 ms 14684 KB Output is correct
18 Correct 7 ms 14684 KB Output is correct
19 Correct 8 ms 14632 KB Output is correct
20 Correct 7 ms 14528 KB Output is correct
21 Correct 11 ms 14684 KB Output is correct
22 Correct 11 ms 14684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9820 KB Output is correct
2 Correct 6 ms 10076 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 4 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 5 ms 10076 KB Output is correct
8 Correct 5 ms 10076 KB Output is correct
9 Correct 5 ms 10076 KB Output is correct
10 Correct 8 ms 9820 KB Output is correct
11 Correct 5 ms 9816 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 4 ms 9832 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 5 ms 10076 KB Output is correct
18 Correct 5 ms 10076 KB Output is correct
19 Correct 6 ms 10076 KB Output is correct
20 Correct 4 ms 10076 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 23892 KB Output is correct
2 Correct 63 ms 24080 KB Output is correct
3 Correct 74 ms 23944 KB Output is correct
4 Correct 70 ms 23992 KB Output is correct
5 Correct 68 ms 23988 KB Output is correct
6 Correct 81 ms 27616 KB Output is correct
7 Correct 86 ms 26456 KB Output is correct
8 Correct 80 ms 25900 KB Output is correct
9 Correct 92 ms 25228 KB Output is correct
10 Correct 70 ms 23836 KB Output is correct
11 Correct 65 ms 24032 KB Output is correct
12 Correct 65 ms 23856 KB Output is correct
13 Correct 67 ms 24036 KB Output is correct
14 Correct 61 ms 23488 KB Output is correct
15 Correct 59 ms 22868 KB Output is correct
16 Correct 48 ms 20596 KB Output is correct
17 Correct 52 ms 24468 KB Output is correct
18 Correct 50 ms 24500 KB Output is correct
19 Correct 54 ms 24740 KB Output is correct
20 Correct 55 ms 24388 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 6 ms 9928 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9952 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 9996 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 7 ms 9996 KB Output is correct
12 Correct 5 ms 9876 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9876 KB Output is correct
16 Correct 5 ms 10000 KB Output is correct
17 Correct 4 ms 9832 KB Output is correct
18 Correct 5 ms 9888 KB Output is correct
19 Correct 4 ms 9824 KB Output is correct
20 Correct 5 ms 9832 KB Output is correct
21 Correct 5 ms 9832 KB Output is correct
22 Correct 4 ms 9832 KB Output is correct
23 Correct 4 ms 9888 KB Output is correct
24 Correct 4 ms 9832 KB Output is correct
25 Correct 4 ms 9832 KB Output is correct
26 Correct 4 ms 9832 KB Output is correct
27 Correct 4 ms 9832 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 23904 KB Output is correct
2 Correct 62 ms 23764 KB Output is correct
3 Correct 58 ms 22368 KB Output is correct
4 Correct 53 ms 20836 KB Output is correct
5 Correct 49 ms 19336 KB Output is correct
6 Correct 50 ms 18528 KB Output is correct
7 Correct 42 ms 18404 KB Output is correct
8 Correct 40 ms 18016 KB Output is correct
9 Correct 39 ms 17940 KB Output is correct
10 Correct 45 ms 17760 KB Output is correct
11 Correct 39 ms 17244 KB Output is correct
12 Correct 36 ms 17208 KB Output is correct
13 Correct 37 ms 17372 KB Output is correct
14 Correct 43 ms 19176 KB Output is correct
15 Correct 61 ms 25940 KB Output is correct
16 Correct 61 ms 24912 KB Output is correct
17 Correct 61 ms 24912 KB Output is correct
18 Correct 61 ms 23892 KB Output is correct
19 Correct 55 ms 21328 KB Output is correct
20 Correct 54 ms 21332 KB Output is correct
21 Correct 56 ms 21180 KB Output is correct
22 Correct 47 ms 20564 KB Output is correct
23 Correct 43 ms 19796 KB Output is correct
24 Correct 53 ms 23112 KB Output is correct
25 Correct 51 ms 23248 KB Output is correct
26 Correct 48 ms 21964 KB Output is correct
27 Correct 56 ms 21920 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9816 KB Output is correct
5 Correct 4 ms 9880 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9880 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9732 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 4 ms 9876 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 7 ms 9820 KB Output is correct
24 Correct 5 ms 9796 KB Output is correct
25 Correct 5 ms 9820 KB Output is correct
26 Correct 5 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9820 KB Output is correct
29 Correct 5 ms 9800 KB Output is correct
30 Correct 7 ms 10072 KB Output is correct
31 Correct 4 ms 9816 KB Output is correct
32 Correct 5 ms 9820 KB Output is correct
33 Correct 4 ms 9816 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 5 ms 9820 KB Output is correct
36 Correct 30 ms 9816 KB Output is correct
37 Correct 127 ms 9816 KB Output is correct
38 Incorrect 691 ms 9816 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9816 KB Output is correct
5 Correct 4 ms 9880 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9880 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9732 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 4 ms 9876 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 7 ms 9820 KB Output is correct
24 Correct 5 ms 9796 KB Output is correct
25 Correct 5 ms 9820 KB Output is correct
26 Correct 5 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct
28 Correct 5 ms 9820 KB Output is correct
29 Correct 5 ms 9800 KB Output is correct
30 Correct 7 ms 10072 KB Output is correct
31 Correct 4 ms 9816 KB Output is correct
32 Correct 5 ms 9820 KB Output is correct
33 Correct 4 ms 9816 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 5 ms 9820 KB Output is correct
36 Correct 30 ms 9816 KB Output is correct
37 Correct 127 ms 9816 KB Output is correct
38 Incorrect 691 ms 9816 KB Output isn't correct
39 Halted 0 ms 0 KB -