oj.uz

Submission #401427

# Submission time Handle Problem Language Result Execution time Memory
401427 2021-05-10T08:33:37 Z Hazem Duathlon (APIO18_duathlon) C++14
31 / 100
 96 ms 21980 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]+1)
            ret += dfs(x,i,sz);
    
    LL cur = sz-1;
    for(auto x:adj[i]){
        
        if(depth[x]==depth[i]+1||x==pre){
            LL v = 0;
            if(x==pre)v = sz-sizes[i];
            else v = sizes[x];
            ret += (cur-v)*v;
        }

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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20724 KB Output is correct
2 Correct 89 ms 21980 KB Output is correct
3 Correct 87 ms 16504 KB Output is correct
4 Correct 96 ms 19180 KB Output is correct
5 Correct 81 ms 14668 KB Output is correct
6 Correct 80 ms 14660 KB Output is correct
7 Correct 74 ms 13124 KB Output is correct
8 Correct 80 ms 14036 KB Output is correct
9 Correct 80 ms 12116 KB Output is correct
10 Correct 75 ms 13080 KB Output is correct
11 Correct 73 ms 10752 KB Output is correct
12 Correct 50 ms 10692 KB Output is correct
13 Correct 66 ms 10588 KB Output is correct
14 Correct 53 ms 10440 KB Output is correct
15 Correct 36 ms 9804 KB Output is correct
16 Correct 41 ms 9760 KB Output is correct
17 Correct 6 ms 6220 KB Output is correct
18 Correct 6 ms 6348 KB Output is correct
19 Correct 6 ms 6220 KB Output is correct
20 Correct 5 ms 6220 KB Output is correct
21 Correct 6 ms 6092 KB Output is correct
22 Correct 6 ms 6092 KB Output is correct

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 5108 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 5060 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 5060 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 5004 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 4 ms 5020 KB Output is correct
17 Correct 5 ms 4940 KB Output is correct
18 Correct 4 ms 4992 KB Output is correct
19 Correct 4 ms 5072 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 77 ms 9776 KB Output is correct
2 Correct 65 ms 9796 KB Output is correct
3 Correct 76 ms 9912 KB Output is correct
4 Correct 66 ms 9884 KB Output is correct
5 Correct 70 ms 9796 KB Output is correct
6 Correct 86 ms 15652 KB Output is correct
7 Correct 82 ms 13736 KB Output is correct
8 Correct 76 ms 12740 KB Output is correct
9 Correct 84 ms 11780 KB Output is correct
10 Correct 80 ms 9884 KB Output is correct
11 Correct 65 ms 9836 KB Output is correct
12 Correct 65 ms 9812 KB Output is correct
13 Correct 72 ms 9896 KB Output is correct
14 Correct 61 ms 9720 KB Output is correct
15 Correct 51 ms 9620 KB Output is correct
16 Correct 31 ms 8908 KB Output is correct
17 Correct 51 ms 10136 KB Output is correct
18 Correct 48 ms 10072 KB Output is correct
19 Correct 44 ms 10096 KB Output is correct
20 Correct 50 ms 10192 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 68 ms 9828 KB Output is correct
2 Correct 69 ms 9796 KB Output is correct
3 Incorrect 80 ms 9836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -