oj.uz

Submission #401466

# Submission time Handle Problem Language Result Execution time Memory
401466 2021-05-10T10:25:46 Z Hazem Duathlon (APIO18_duathlon) C++14
31 / 100
 127 ms 23792 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],mx[N],mn[N],n,m,par[N];
bool vis[N];

int dfs1(int i,int pre){

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

        else if(x!=pre){
            int cur = i;
            while(depth[cur]>=depth[x])mx[cur] = x,mn[cur] = i,cur = par[cur];
        }

    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)*4;
            ret += (sz-sizes[mx[i]]+1)*(sizes[mx[i]]-sizes[i]-len+1)*2;
            ret += (sizes[mx[i]]-sizes[i]-len+1)*(sizes[i])*2;
        }
    }

        if(mx[i]&&mx[i]!=i){
            LL len = -depth[mx[i]]+depth[i]-1;
            ret += len*(sz-sizes[mx[i]])*2;
        }

        if(mn[i]&&mn[i]!=i){
            LL len = depth[mn[i]]-depth[i]-1;
            ret += len*(sizes[mn[i]]-1)*2;
        }

    return ret;
}

bool vis1[N];

bool check(int v1,int v2,int v3,int i){

    if(vis1[i])
        return 0;

    if(i==v3)
        return vis1[v2];
    
    vis1[i] = 1;
    bool ret = 0;
    for(auto x:adj[i])
        ret |= check(v1,v2,v3,x);

    vis1[i] = 0;
    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);        
    }

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

    // LL ans1 = 0;
    // for(int i=1;i<=n;i++)
    //     for(int j=1;j<=n;j++)
    //         for(int k=1;k<=n;k++)
    //             if(i!=j&&i!=k&&j!=k)
    //                 ans1 += check(i,j,k,i);

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

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 105 ms 23164 KB Output is correct
2 Correct 127 ms 23792 KB Output is correct
3 Correct 95 ms 18372 KB Output is correct
4 Correct 99 ms 21028 KB Output is correct
5 Correct 93 ms 16556 KB Output is correct
6 Correct 97 ms 16548 KB Output is correct
7 Correct 117 ms 14996 KB Output is correct
8 Correct 124 ms 15940 KB Output is correct
9 Correct 82 ms 13996 KB Output is correct
10 Correct 92 ms 14944 KB Output is correct
11 Correct 67 ms 12868 KB Output is correct
12 Correct 66 ms 12716 KB Output is correct
13 Correct 55 ms 12740 KB Output is correct
14 Correct 53 ms 12592 KB Output is correct
15 Correct 42 ms 12216 KB Output is correct
16 Correct 45 ms 12184 KB Output is correct
17 Correct 8 ms 7116 KB Output is correct
18 Correct 7 ms 7148 KB Output is correct
19 Correct 7 ms 6988 KB Output is correct
20 Correct 8 ms 7056 KB Output is correct
21 Correct 6 ms 6924 KB Output is correct
22 Correct 7 ms 6988 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5060 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5136 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 5068 KB Output is correct
11 Correct 5 ms 5108 KB Output is correct
12 Correct 5 ms 5068 KB Output is correct
13 Correct 4 ms 5012 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 4 ms 5008 KB Output is correct
17 Correct 4 ms 5068 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 5012 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10612 KB Output is correct
2 Correct 82 ms 11756 KB Output is correct
3 Correct 79 ms 11568 KB Output is correct
4 Correct 75 ms 11648 KB Output is correct
5 Correct 94 ms 11588 KB Output is correct
6 Correct 93 ms 17532 KB Output is correct
7 Correct 91 ms 15456 KB Output is correct
8 Correct 88 ms 14540 KB Output is correct
9 Correct 99 ms 13636 KB Output is correct
10 Correct 75 ms 11596 KB Output is correct
11 Correct 74 ms 11440 KB Output is correct
12 Correct 70 ms 11460 KB Output is correct
13 Correct 100 ms 11524 KB Output is correct
14 Correct 71 ms 11436 KB Output is correct
15 Correct 52 ms 11308 KB Output is correct
16 Correct 35 ms 10424 KB Output is correct
17 Correct 55 ms 11720 KB Output is correct
18 Correct 49 ms 11724 KB Output is correct
19 Correct 82 ms 11828 KB Output is correct
20 Correct 60 ms 11824 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Incorrect 4 ms 5068 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 10592 KB Output is correct
2 Correct 81 ms 11628 KB Output is correct
3 Incorrect 93 ms 13080 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 -