oj.uz

Submission #401426

# Submission time Handle Problem Language Result Execution time Memory
401426 2021-05-10T08:17:36 Z Hazem Duathlon (APIO18_duathlon) C++14
23 / 100
 126 ms 19120 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 C(LL n,LL k){

    LL ret = 1,d = 1;
    for(int i=n;i>=n-k+1;i--)
        ret = ret*i,d *= n-i+1;

    return ret/d;
}

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]){
        
        if(depth[x]>depth[i]||x==pre){
            LL v = 0;
            if(x==pre)v = sz-sizes[i];
            else v = sizes[x];
            ret += (cur-v)*v;
        }

        else {
            LL len = depth[i]-depth[x]+1;
            ret += C(len,3)*2;
            ret += C(len-1,2)*(sz-sizes[x]+1);
        }
    }

    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:74:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   74 |     scanf("%d%d",&n,&m);
      |            ~^    ~~
      |             |    |
      |             int* long long int*
      |            %lld
count_triplets.cpp:74:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   74 |     scanf("%d%d",&n,&m);
      |              ~^     ~~
      |               |     |
      |               int*  long long int*
      |              %lld
count_triplets.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         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 89 ms 19120 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 5 ms 5056 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 5 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 5 ms 5068 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 4940 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 5068 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9796 KB Output is correct
2 Correct 68 ms 9792 KB Output is correct
3 Correct 64 ms 9888 KB Output is correct
4 Correct 66 ms 9796 KB Output is correct
5 Correct 66 ms 9884 KB Output is correct
6 Correct 83 ms 14804 KB Output is correct
7 Correct 79 ms 13124 KB Output is correct
8 Correct 82 ms 12288 KB Output is correct
9 Correct 74 ms 11460 KB Output is correct
10 Correct 67 ms 9880 KB Output is correct
11 Correct 66 ms 9900 KB Output is correct
12 Correct 63 ms 9856 KB Output is correct
13 Correct 63 ms 9804 KB Output is correct
14 Correct 54 ms 9796 KB Output is correct
15 Correct 47 ms 9668 KB Output is correct
16 Correct 32 ms 8900 KB Output is correct
17 Correct 43 ms 10140 KB Output is correct
18 Correct 44 ms 10188 KB Output is correct
19 Correct 44 ms 10080 KB Output is correct
20 Correct 46 ms 10112 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 5 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 68 ms 9832 KB Output is correct
2 Correct 72 ms 9744 KB Output is correct
3 Incorrect 126 ms 9756 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 -