oj.uz

Submission #401425

# Submission time Handle Problem Language Result Execution time Memory
401425 2021-05-10T08:12:33 Z Hazem Duathlon (APIO18_duathlon) C++14
23 / 100
 92 ms 17640 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 2e5+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 1e14;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

vector<int>adj[N];
LL sizes[N],depth[N],n,m;
bool vis[N];

int dfs1(int i,int pre){

    vis[i] = 1;
    sizes[i] = vis[i] = 1;
    for(auto x:adj[i])
        if(!vis[x])
            depth[x] = depth[i]+1,sizes[i] += dfs1(x,i);

    return sizes[i];
}

LL dfs(int i,int pre,int sz){

    LL ret = 0;
    for(auto x:adj[i]){
        if(depth[x]<depth[i])continue;
        ret += dfs(x,i,sz);
    }

    LL cur = sz-1;
    for(auto x:adj[i]){
        LL v = 0;
        if(x==pre)v = sz-sizes[i];
        else v = sizes[x];
        ret += (cur-v)*v;
    }

    return ret;
}

int main(){

    //freopen("out.txt","w",stdout);
    //freopen("out.txt","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);        
    }

    LL ans = 0;
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            int sz = dfs1(i,i);
            ans += dfs(i,i,sz);
        }

    printf("%lld\n",ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:56:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   56 |     scanf("%d%d",&n,&m);
      |            ~^    ~~
      |             |    |
      |             int* long long int*
      |            %lld
count_triplets.cpp:56:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   56 |     scanf("%d%d",&n,&m);
      |              ~^     ~~
      |               |     |
      |               int*  long long int*
      |              %lld
count_triplets.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 17640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5064 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 5000 KB Output is correct
13 Correct 4 ms 5068 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 5008 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5004 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 4 ms 5000 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9976 KB Output is correct
2 Correct 70 ms 9924 KB Output is correct
3 Correct 73 ms 9924 KB Output is correct
4 Correct 65 ms 9912 KB Output is correct
5 Correct 72 ms 9964 KB Output is correct
6 Correct 84 ms 14112 KB Output is correct
7 Correct 76 ms 12632 KB Output is correct
8 Correct 83 ms 11928 KB Output is correct
9 Correct 76 ms 11244 KB Output is correct
10 Correct 65 ms 9944 KB Output is correct
11 Correct 64 ms 9924 KB Output is correct
12 Correct 67 ms 9904 KB Output is correct
13 Correct 63 ms 9868 KB Output is correct
14 Correct 54 ms 9868 KB Output is correct
15 Correct 50 ms 9744 KB Output is correct
16 Correct 35 ms 9092 KB Output is correct
17 Correct 45 ms 10200 KB Output is correct
18 Correct 50 ms 10192 KB Output is correct
19 Correct 45 ms 10168 KB Output is correct
20 Correct 49 ms 10180 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Incorrect 4 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9796 KB Output is correct
2 Correct 80 ms 9844 KB Output is correct
3 Incorrect 92 ms 10020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -