oj.uz

Submission #866134

# Submission time Handle Problem Language Result Execution time Memory
866134 2023-10-25T13:06:44 Z alexander707070 Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

long long n,m,a,b;
long long sz[MAXN],comp[MAXN];
vector<int> v[MAXN];

long long ans;

void dfs(int x,int p){

    sz[x]=1;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x);
        sz[x]+=sz[v[x][i]];
    }
}

void dfs2(int x,int p,int s){

    comp[x]=s;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs2(v[x][i],x,s);
    }
}

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>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=1;i<=n;i++){
        if(sz[i]==0){
            dfs(i,0); dfs2(i,0,sz[i]);
        }
    }

    for(long long i=1;i<=n;i++){
        ans+=(comp[i]-1)*(comp[i]-2);
        for(int f=0;f<v[i].size();f++){
            if(sz[v[i][f]]<sz[i]){
                ans-=sz[v[i][f]]*(sz[v[i][f]]-1);
            }else{
                ans-=(comp[i]-sz[i])*(comp[i]-sz[i]-1);
            }
        }
    }

    cout<<ans<<"\n";

    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int, int)':
count_triplets.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int f=0;f<v[i].size();f++){
      |                     ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 576 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 576 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 1022620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2904 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2732 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7520 KB Output is correct
2 Correct 29 ms 7516 KB Output is correct
3 Correct 31 ms 7516 KB Output is correct
4 Correct 29 ms 7504 KB Output is correct
5 Correct 28 ms 7512 KB Output is correct
6 Correct 32 ms 10844 KB Output is correct
7 Correct 37 ms 9564 KB Output is correct
8 Correct 36 ms 9164 KB Output is correct
9 Correct 31 ms 8532 KB Output is correct
10 Correct 28 ms 7512 KB Output is correct
11 Correct 29 ms 8792 KB Output is correct
12 Correct 29 ms 8796 KB Output is correct
13 Correct 29 ms 8796 KB Output is correct
14 Correct 32 ms 8412 KB Output is correct
15 Correct 24 ms 8284 KB Output is correct
16 Correct 16 ms 7348 KB Output is correct
17 Correct 20 ms 9280 KB Output is correct
18 Correct 21 ms 9044 KB Output is correct
19 Correct 22 ms 9004 KB Output is correct
20 Correct 21 ms 9064 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Runtime error 667 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7760 KB Output is correct
2 Correct 29 ms 7516 KB Output is correct
3 Runtime error 751 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 576 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 576 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -