oj.uz

답안 #1087788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087788 2024-09-13T08:38:13 Z alexander707070 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 69 ms 26872 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);
}

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

    if(ans%2==1)cout<<1/0;

    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 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 'int main()':
count_triplets.cpp:112:24: warning: division by zero [-Wdiv-by-zero]
  112 |     if(ans%2==1)cout<<1/0;
      |                       ~^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 23888 KB Output is correct
2 Correct 45 ms 23892 KB Output is correct
3 Correct 57 ms 23352 KB Output is correct
4 Correct 47 ms 23632 KB Output is correct
5 Correct 46 ms 20896 KB Output is correct
6 Correct 51 ms 22356 KB Output is correct
7 Correct 51 ms 21584 KB Output is correct
8 Correct 52 ms 22108 KB Output is correct
9 Correct 50 ms 20820 KB Output is correct
10 Correct 48 ms 20816 KB Output is correct
11 Correct 63 ms 19536 KB Output is correct
12 Correct 38 ms 19536 KB Output is correct
13 Correct 36 ms 19792 KB Output is correct
14 Correct 41 ms 19540 KB Output is correct
15 Correct 30 ms 19312 KB Output is correct
16 Correct 42 ms 19024 KB Output is correct
17 Correct 8 ms 14684 KB Output is correct
18 Correct 8 ms 14504 KB Output is correct
19 Correct 7 ms 14684 KB Output is correct
20 Correct 8 ms 14684 KB Output is correct
21 Correct 8 ms 14584 KB Output is correct
22 Correct 7 ms 14680 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 10004 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 5 ms 10072 KB Output is correct
6 Correct 4 ms 9976 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 9820 KB Output is correct
10 Correct 4 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 4 ms 9820 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 9816 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

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 23444 KB Output is correct
2 Correct 54 ms 23124 KB Output is correct
3 Correct 69 ms 23312 KB Output is correct
4 Correct 55 ms 23124 KB Output is correct
5 Correct 57 ms 23120 KB Output is correct
6 Correct 66 ms 26872 KB Output is correct
7 Correct 66 ms 25680 KB Output is correct
8 Correct 68 ms 24912 KB Output is correct
9 Correct 59 ms 24380 KB Output is correct
10 Correct 52 ms 23124 KB Output is correct
11 Correct 55 ms 23328 KB Output is correct
12 Correct 54 ms 23124 KB Output is correct
13 Correct 54 ms 23120 KB Output is correct
14 Correct 50 ms 22608 KB Output is correct
15 Correct 44 ms 22104 KB Output is correct
16 Correct 32 ms 20264 KB Output is correct
17 Correct 40 ms 23744 KB Output is correct
18 Correct 39 ms 23716 KB Output is correct
19 Correct 41 ms 23996 KB Output is correct
20 Correct 44 ms 23620 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 23120 KB Output is correct
2 Correct 61 ms 23120 KB Output is correct
3 Incorrect 56 ms 21384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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