oj.uz

답안 #1087879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087879 2024-09-13T10:50:05 Z alexander707070 철인 이종 경기 (APIO18_duathlon) C++14
71 / 100
 1000 ms 27980 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<=5;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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 6 ms 9832 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 6 ms 9836 KB Output is correct
12 Correct 6 ms 9820 KB Output is correct
13 Correct 10 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9888 KB Output is correct
16 Correct 6 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 9 ms 9876 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9720 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 6 ms 9888 KB Output is correct
23 Correct 5 ms 9816 KB Output is correct
24 Correct 5 ms 9820 KB Output is correct
25 Correct 6 ms 9820 KB Output is correct
26 Correct 7 ms 9820 KB Output is correct
27 Correct 5 ms 9820 KB Output is correct
28 Correct 6 ms 9820 KB Output is correct
29 Correct 6 ms 9820 KB Output is correct
30 Correct 4 ms 9820 KB Output is correct
31 Correct 4 ms 9668 KB Output is correct
32 Correct 6 ms 9820 KB Output is correct
33 Correct 5 ms 9836 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9820 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 6 ms 9832 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 6 ms 9836 KB Output is correct
12 Correct 6 ms 9820 KB Output is correct
13 Correct 10 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9888 KB Output is correct
16 Correct 6 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 9 ms 9876 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9720 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 6 ms 9888 KB Output is correct
23 Correct 5 ms 9816 KB Output is correct
24 Correct 5 ms 9820 KB Output is correct
25 Correct 6 ms 9820 KB Output is correct
26 Correct 7 ms 9820 KB Output is correct
27 Correct 5 ms 9820 KB Output is correct
28 Correct 6 ms 9820 KB Output is correct
29 Correct 6 ms 9820 KB Output is correct
30 Correct 4 ms 9820 KB Output is correct
31 Correct 4 ms 9668 KB Output is correct
32 Correct 6 ms 9820 KB Output is correct
33 Correct 5 ms 9836 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9820 KB Output is correct
36 Correct 47 ms 9820 KB Output is correct
37 Correct 209 ms 9864 KB Output is correct
38 Execution timed out 1071 ms 9876 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 25180 KB Output is correct
2 Correct 42 ms 25172 KB Output is correct
3 Correct 50 ms 24400 KB Output is correct
4 Correct 47 ms 24916 KB Output is correct
5 Correct 49 ms 22220 KB Output is correct
6 Correct 58 ms 23636 KB Output is correct
7 Correct 57 ms 22872 KB Output is correct
8 Correct 57 ms 23376 KB Output is correct
9 Correct 53 ms 22096 KB Output is correct
10 Correct 56 ms 22168 KB Output is correct
11 Correct 45 ms 20560 KB Output is correct
12 Correct 44 ms 20440 KB Output is correct
13 Correct 40 ms 20560 KB Output is correct
14 Correct 41 ms 20376 KB Output is correct
15 Correct 35 ms 20152 KB Output is correct
16 Correct 33 ms 19804 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 9 ms 14536 KB Output is correct
21 Correct 8 ms 14684 KB Output is correct
22 Correct 8 ms 14684 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 5 ms 9832 KB Output is correct
3 Correct 5 ms 9924 KB Output is correct
4 Correct 5 ms 10072 KB Output is correct
5 Correct 5 ms 10076 KB Output is correct
6 Correct 4 ms 9904 KB Output is correct
7 Correct 4 ms 10072 KB Output is correct
8 Correct 5 ms 10076 KB Output is correct
9 Correct 5 ms 9904 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Correct 4 ms 9816 KB Output is correct
13 Correct 4 ms 10068 KB Output is correct
14 Correct 4 ms 9816 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 9816 KB Output is correct
18 Correct 4 ms 10076 KB Output is correct
19 Correct 4 ms 10076 KB Output is correct
20 Correct 4 ms 10076 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 24568 KB Output is correct
2 Correct 57 ms 24400 KB Output is correct
3 Correct 57 ms 24400 KB Output is correct
4 Correct 56 ms 24400 KB Output is correct
5 Correct 58 ms 24404 KB Output is correct
6 Correct 61 ms 27980 KB Output is correct
7 Correct 68 ms 26960 KB Output is correct
8 Correct 65 ms 26228 KB Output is correct
9 Correct 60 ms 25680 KB Output is correct
10 Correct 58 ms 24576 KB Output is correct
11 Correct 55 ms 24464 KB Output is correct
12 Correct 68 ms 24392 KB Output is correct
13 Correct 59 ms 24400 KB Output is correct
14 Correct 53 ms 23892 KB Output is correct
15 Correct 50 ms 23120 KB Output is correct
16 Correct 34 ms 20816 KB Output is correct
17 Correct 42 ms 25032 KB Output is correct
18 Correct 39 ms 24836 KB Output is correct
19 Correct 41 ms 25276 KB Output is correct
20 Correct 41 ms 24900 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 9884 KB Output is correct
5 Correct 6 ms 10016 KB Output is correct
6 Correct 4 ms 9872 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9900 KB Output is correct
9 Correct 5 ms 9820 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 10076 KB Output is correct
13 Correct 5 ms 10076 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 4 ms 9816 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 9820 KB Output is correct
19 Correct 4 ms 9820 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 10060 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Correct 4 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

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 24320 KB Output is correct
2 Correct 54 ms 24148 KB Output is correct
3 Correct 57 ms 22868 KB Output is correct
4 Correct 51 ms 21328 KB Output is correct
5 Correct 53 ms 19684 KB Output is correct
6 Correct 43 ms 19032 KB Output is correct
7 Correct 41 ms 18512 KB Output is correct
8 Correct 39 ms 18260 KB Output is correct
9 Correct 38 ms 18004 KB Output is correct
10 Correct 38 ms 18000 KB Output is correct
11 Correct 37 ms 17756 KB Output is correct
12 Correct 36 ms 17792 KB Output is correct
13 Correct 37 ms 17748 KB Output is correct
14 Correct 38 ms 19480 KB Output is correct
15 Correct 67 ms 25936 KB Output is correct
16 Correct 60 ms 24912 KB Output is correct
17 Correct 57 ms 24916 KB Output is correct
18 Correct 63 ms 23752 KB Output is correct
19 Correct 64 ms 21332 KB Output is correct
20 Correct 53 ms 21332 KB Output is correct
21 Correct 53 ms 21328 KB Output is correct
22 Correct 48 ms 20720 KB Output is correct
23 Correct 43 ms 19792 KB Output is correct
24 Correct 47 ms 23000 KB Output is correct
25 Correct 57 ms 23104 KB Output is correct
26 Correct 49 ms 21960 KB Output is correct
27 Correct 51 ms 22100 KB Output is correct

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 6 ms 9832 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 6 ms 9836 KB Output is correct
12 Correct 6 ms 9820 KB Output is correct
13 Correct 10 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9888 KB Output is correct
16 Correct 6 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 9 ms 9876 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9720 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 6 ms 9888 KB Output is correct
23 Correct 5 ms 9816 KB Output is correct
24 Correct 5 ms 9820 KB Output is correct
25 Correct 6 ms 9820 KB Output is correct
26 Correct 7 ms 9820 KB Output is correct
27 Correct 5 ms 9820 KB Output is correct
28 Correct 6 ms 9820 KB Output is correct
29 Correct 6 ms 9820 KB Output is correct
30 Correct 4 ms 9820 KB Output is correct
31 Correct 4 ms 9668 KB Output is correct
32 Correct 6 ms 9820 KB Output is correct
33 Correct 5 ms 9836 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9820 KB Output is correct
36 Correct 47 ms 9820 KB Output is correct
37 Correct 209 ms 9864 KB Output is correct
38 Execution timed out 1071 ms 9876 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 4 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 6 ms 9832 KB Output is correct
8 Correct 6 ms 9868 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 6 ms 9836 KB Output is correct
12 Correct 6 ms 9820 KB Output is correct
13 Correct 10 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 5 ms 9888 KB Output is correct
16 Correct 6 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 9 ms 9876 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9720 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 6 ms 9888 KB Output is correct
23 Correct 5 ms 9816 KB Output is correct
24 Correct 5 ms 9820 KB Output is correct
25 Correct 6 ms 9820 KB Output is correct
26 Correct 7 ms 9820 KB Output is correct
27 Correct 5 ms 9820 KB Output is correct
28 Correct 6 ms 9820 KB Output is correct
29 Correct 6 ms 9820 KB Output is correct
30 Correct 4 ms 9820 KB Output is correct
31 Correct 4 ms 9668 KB Output is correct
32 Correct 6 ms 9820 KB Output is correct
33 Correct 5 ms 9836 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9820 KB Output is correct
36 Correct 47 ms 9820 KB Output is correct
37 Correct 209 ms 9864 KB Output is correct
38 Execution timed out 1071 ms 9876 KB Time limit exceeded
39 Halted 0 ms 0 KB -