oj.uz

답안 #866161

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866161 2023-10-25T13:43:59 Z alexander707070 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 85 ms 31836 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;

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

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

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

void dfs3(int x,int p,int t){
    total[x]=t;

    for(int i=0;i<tree[x].size();i++){
        if(tree[x][i]==p)continue;
        dfs3(tree[x][i],x,t);
    }
}

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

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

    for(int i=1;i<=k;i++){
        ans+=(total[i]-szcomp[i])*(total[i]-szcomp[i]-1)*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)*szcomp[i];
            }else{
                ans-=(total[i]-sz[i])*(total[i]-sz[i]-1)*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:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs3(int, int, int)':
count_triplets.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<tree[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int f=0;f<tree[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20972 KB Output is correct
3 Correct 4 ms 20828 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 20972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20972 KB Output is correct
3 Correct 4 ms 20828 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 20972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 31836 KB Output is correct
2 Correct 44 ms 31828 KB Output is correct
3 Correct 52 ms 29716 KB Output is correct
4 Correct 52 ms 30732 KB Output is correct
5 Correct 45 ms 27740 KB Output is correct
6 Correct 58 ms 28500 KB Output is correct
7 Correct 50 ms 27592 KB Output is correct
8 Correct 49 ms 28240 KB Output is correct
9 Correct 49 ms 26712 KB Output is correct
10 Correct 48 ms 27144 KB Output is correct
11 Correct 44 ms 25692 KB Output is correct
12 Correct 38 ms 25676 KB Output is correct
13 Correct 36 ms 25684 KB Output is correct
14 Correct 36 ms 25584 KB Output is correct
15 Correct 30 ms 25168 KB Output is correct
16 Correct 30 ms 25180 KB Output is correct
17 Correct 5 ms 20828 KB Output is correct
18 Correct 5 ms 20992 KB Output is correct
19 Correct 6 ms 20828 KB Output is correct
20 Correct 5 ms 20928 KB Output is correct
21 Correct 5 ms 20824 KB Output is correct
22 Correct 6 ms 20828 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20920 KB Output is correct
3 Correct 4 ms 20824 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 5 ms 20932 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20828 KB Output is correct
12 Correct 3 ms 20828 KB Output is correct
13 Correct 4 ms 20828 KB Output is correct
14 Correct 4 ms 20932 KB Output is correct
15 Correct 4 ms 20828 KB Output is correct
16 Correct 3 ms 20828 KB Output is correct
17 Correct 4 ms 20828 KB Output is correct
18 Correct 3 ms 20828 KB Output is correct
19 Correct 4 ms 20828 KB Output is correct
20 Correct 4 ms 20828 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 27984 KB Output is correct
2 Correct 59 ms 28100 KB Output is correct
3 Correct 61 ms 28084 KB Output is correct
4 Correct 55 ms 27988 KB Output is correct
5 Correct 56 ms 28048 KB Output is correct
6 Correct 61 ms 31488 KB Output is correct
7 Correct 85 ms 30612 KB Output is correct
8 Correct 67 ms 29776 KB Output is correct
9 Correct 56 ms 29008 KB Output is correct
10 Correct 52 ms 27988 KB Output is correct
11 Correct 55 ms 28092 KB Output is correct
12 Correct 58 ms 27916 KB Output is correct
13 Correct 54 ms 27928 KB Output is correct
14 Correct 49 ms 27476 KB Output is correct
15 Correct 51 ms 27228 KB Output is correct
16 Correct 34 ms 25748 KB Output is correct
17 Correct 40 ms 28360 KB Output is correct
18 Correct 38 ms 28480 KB Output is correct
19 Correct 40 ms 28868 KB Output is correct
20 Correct 39 ms 28484 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 21004 KB Output is correct
3 Incorrect 5 ms 21088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 27924 KB Output is correct
2 Correct 56 ms 27732 KB Output is correct
3 Incorrect 54 ms 27048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20972 KB Output is correct
3 Correct 4 ms 20828 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 20972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20972 KB Output is correct
3 Correct 4 ms 20828 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 20972 KB Output isn't correct
8 Halted 0 ms 0 KB -