oj.uz

Submission #1087882

# Submission time Handle Problem Language Result Execution time Memory
1087882 2024-09-13T10:50:52 Z alexander707070 Duathlon (APIO18_duathlon) C++14
71 / 100
 712 ms 27728 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<5){
            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 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9888 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9868 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9864 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 9864 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9760 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 5 ms 9820 KB Output is correct
24 Correct 5 ms 9816 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 4 ms 9820 KB Output is correct
29 Correct 5 ms 9856 KB Output is correct
30 Correct 6 ms 9800 KB Output is correct
31 Correct 5 ms 9820 KB Output is correct
32 Correct 6 ms 9652 KB Output is correct
33 Correct 5 ms 9784 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9876 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9888 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9868 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9864 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 9864 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9760 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 5 ms 9820 KB Output is correct
24 Correct 5 ms 9816 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 4 ms 9820 KB Output is correct
29 Correct 5 ms 9856 KB Output is correct
30 Correct 6 ms 9800 KB Output is correct
31 Correct 5 ms 9820 KB Output is correct
32 Correct 6 ms 9652 KB Output is correct
33 Correct 5 ms 9784 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9876 KB Output is correct
36 Correct 34 ms 9816 KB Output is correct
37 Correct 132 ms 9820 KB Output is correct
38 Incorrect 712 ms 9872 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 25172 KB Output is correct
2 Correct 41 ms 25180 KB Output is correct
3 Correct 50 ms 24400 KB Output is correct
4 Correct 46 ms 25024 KB Output is correct
5 Correct 49 ms 21880 KB Output is correct
6 Correct 51 ms 23376 KB Output is correct
7 Correct 52 ms 22612 KB Output is correct
8 Correct 51 ms 23124 KB Output is correct
9 Correct 51 ms 21888 KB Output is correct
10 Correct 50 ms 21844 KB Output is correct
11 Correct 43 ms 20484 KB Output is correct
12 Correct 45 ms 20300 KB Output is correct
13 Correct 38 ms 20308 KB Output is correct
14 Correct 40 ms 20244 KB Output is correct
15 Correct 34 ms 20060 KB Output is correct
16 Correct 33 ms 19920 KB Output is correct
17 Correct 8 ms 14680 KB Output is correct
18 Correct 8 ms 14684 KB Output is correct
19 Correct 8 ms 14684 KB Output is correct
20 Correct 8 ms 14684 KB Output is correct
21 Correct 8 ms 14684 KB Output is correct
22 Correct 9 ms 14640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10076 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 4 ms 10104 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 5 ms 10328 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 5 ms 10076 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 4 ms 10076 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 10056 KB Output is correct
16 Correct 5 ms 10036 KB Output is correct
17 Correct 4 ms 9820 KB Output is correct
18 Correct 5 ms 9872 KB Output is correct
19 Correct 7 ms 10076 KB Output is correct
20 Correct 5 ms 9912 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 24316 KB Output is correct
2 Correct 67 ms 24192 KB Output is correct
3 Correct 67 ms 24308 KB Output is correct
4 Correct 60 ms 24148 KB Output is correct
5 Correct 59 ms 24236 KB Output is correct
6 Correct 68 ms 27728 KB Output is correct
7 Correct 69 ms 26704 KB Output is correct
8 Correct 63 ms 25936 KB Output is correct
9 Correct 61 ms 25424 KB Output is correct
10 Correct 69 ms 24148 KB Output is correct
11 Correct 55 ms 24296 KB Output is correct
12 Correct 54 ms 24148 KB Output is correct
13 Correct 56 ms 24224 KB Output is correct
14 Correct 49 ms 23632 KB Output is correct
15 Correct 46 ms 22864 KB Output is correct
16 Correct 32 ms 20816 KB Output is correct
17 Correct 38 ms 24572 KB Output is correct
18 Correct 38 ms 24644 KB Output is correct
19 Correct 39 ms 25024 KB Output is correct
20 Correct 40 ms 24652 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9872 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9924 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9832 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 7 ms 9820 KB Output is correct
12 Correct 4 ms 10076 KB Output is correct
13 Correct 4 ms 10076 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 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 4 ms 9820 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 4 ms 9816 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 5 ms 9820 KB Output is correct
24 Correct 6 ms 9820 KB Output is correct
25 Correct 4 ms 9820 KB Output is correct
26 Correct 4 ms 9820 KB Output is correct
27 Correct 4 ms 9820 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 24400 KB Output is correct
2 Correct 59 ms 24144 KB Output is correct
3 Correct 67 ms 22612 KB Output is correct
4 Correct 58 ms 21076 KB Output is correct
5 Correct 47 ms 19288 KB Output is correct
6 Correct 48 ms 18840 KB Output is correct
7 Correct 44 ms 18256 KB Output is correct
8 Correct 43 ms 18036 KB Output is correct
9 Correct 43 ms 17744 KB Output is correct
10 Correct 43 ms 17748 KB Output is correct
11 Correct 38 ms 17492 KB Output is correct
12 Correct 40 ms 17492 KB Output is correct
13 Correct 38 ms 17500 KB Output is correct
14 Correct 42 ms 18772 KB Output is correct
15 Correct 62 ms 24404 KB Output is correct
16 Correct 69 ms 23376 KB Output is correct
17 Correct 60 ms 23364 KB Output is correct
18 Correct 57 ms 22352 KB Output is correct
19 Correct 51 ms 19796 KB Output is correct
20 Correct 51 ms 19796 KB Output is correct
21 Correct 51 ms 19792 KB Output is correct
22 Correct 55 ms 19284 KB Output is correct
23 Correct 49 ms 18696 KB Output is correct
24 Correct 47 ms 21688 KB Output is correct
25 Correct 48 ms 21708 KB Output is correct
26 Correct 45 ms 20428 KB Output is correct
27 Correct 48 ms 20564 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9888 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9868 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9864 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 9864 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9760 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 5 ms 9820 KB Output is correct
24 Correct 5 ms 9816 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 4 ms 9820 KB Output is correct
29 Correct 5 ms 9856 KB Output is correct
30 Correct 6 ms 9800 KB Output is correct
31 Correct 5 ms 9820 KB Output is correct
32 Correct 6 ms 9652 KB Output is correct
33 Correct 5 ms 9784 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9876 KB Output is correct
36 Correct 34 ms 9816 KB Output is correct
37 Correct 132 ms 9820 KB Output is correct
38 Incorrect 712 ms 9872 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9888 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 5 ms 9868 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9864 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 9864 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9760 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct
23 Correct 5 ms 9820 KB Output is correct
24 Correct 5 ms 9816 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 4 ms 9820 KB Output is correct
29 Correct 5 ms 9856 KB Output is correct
30 Correct 6 ms 9800 KB Output is correct
31 Correct 5 ms 9820 KB Output is correct
32 Correct 6 ms 9652 KB Output is correct
33 Correct 5 ms 9784 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9876 KB Output is correct
36 Correct 34 ms 9816 KB Output is correct
37 Correct 132 ms 9820 KB Output is correct
38 Incorrect 712 ms 9872 KB Output isn't correct
39 Halted 0 ms 0 KB -