oj.uz

Submission #401478

# Submission time Handle Problem Language Result Execution time Memory
401478 2021-05-10T11:11:02 Z Hazem Duathlon (APIO18_duathlon) C++14
31 / 100
 111 ms 23128 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;
            
            LL val = 0;
            for(auto x:adj[mx[i]])
                if(depth[x]==depth[mx[i]]+1&&mx[x]!=mx[i])
                    val += sizes[x];

            ret += (sz-sizes[mx[i]]+1+val)*(sizes[mx[i]]-sizes[i]-len+1-val)*2;
            ret += (sizes[mx[i]]-val-sizes[i]-len+1)*(sizes[i])*2;
        }
    }

        if(mx[i]&&mx[i]!=i){
            LL val = 0;
            for(auto x:adj[mx[i]])
                if(depth[x]==depth[mx[i]]+1&&mx[x]!=mx[i])
                    val += sizes[x];

            LL len = -depth[mx[i]]+depth[i]-1;
            ret += len*(sz-sizes[mx[i]]+val)*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:119:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  119 |     scanf("%d%d",&n,&m);
      |            ~^    ~~
      |             |    |
      |             int* long long int*
      |            %lld
count_triplets.cpp:119:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
  119 |     scanf("%d%d",&n,&m);
      |              ~^     ~~
      |               |     |
      |               int*  long long int*
      |              %lld
count_triplets.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |         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 94 ms 23128 KB Output is correct
2 Correct 102 ms 23056 KB Output is correct
3 Correct 101 ms 17604 KB Output is correct
4 Correct 87 ms 20244 KB Output is correct
5 Correct 97 ms 15752 KB Output is correct
6 Correct 91 ms 15796 KB Output is correct
7 Correct 111 ms 14276 KB Output is correct
8 Correct 91 ms 15092 KB Output is correct
9 Correct 83 ms 13124 KB Output is correct
10 Correct 103 ms 14228 KB Output is correct
11 Correct 58 ms 12104 KB Output is correct
12 Correct 55 ms 11972 KB Output is correct
13 Correct 55 ms 11968 KB Output is correct
14 Correct 52 ms 11820 KB Output is correct
15 Correct 41 ms 11580 KB Output is correct
16 Correct 60 ms 11460 KB Output is correct
17 Correct 7 ms 7116 KB Output is correct
18 Correct 6 ms 7116 KB Output is correct
19 Correct 6 ms 6988 KB Output is correct
20 Correct 6 ms 6988 KB Output is correct
21 Correct 6 ms 6988 KB Output is correct
22 Correct 6 ms 6860 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 5048 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 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5088 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 4 ms 5068 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 5068 KB Output is correct
16 Correct 4 ms 5068 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 5100 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 10684 KB Output is correct
2 Correct 81 ms 10700 KB Output is correct
3 Correct 80 ms 10692 KB Output is correct
4 Correct 70 ms 10608 KB Output is correct
5 Correct 94 ms 10608 KB Output is correct
6 Correct 87 ms 16532 KB Output is correct
7 Correct 86 ms 14468 KB Output is correct
8 Correct 79 ms 13504 KB Output is correct
9 Correct 86 ms 12512 KB Output is correct
10 Correct 68 ms 10656 KB Output is correct
11 Correct 72 ms 10692 KB Output is correct
12 Correct 69 ms 10692 KB Output is correct
13 Correct 74 ms 10772 KB Output is correct
14 Correct 66 ms 10600 KB Output is correct
15 Correct 58 ms 10364 KB Output is correct
16 Correct 33 ms 9768 KB Output is correct
17 Correct 44 ms 10940 KB Output is correct
18 Correct 45 ms 10948 KB Output is correct
19 Correct 46 ms 10916 KB Output is correct
20 Correct 53 ms 10888 KB Output is correct

Subtask #6
0 / 15.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 Incorrect 4 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 10692 KB Output is correct
2 Correct 92 ms 10644 KB Output is correct
3 Correct 95 ms 12212 KB Output is correct
4 Incorrect 100 ms 13636 KB Output isn't correct
5 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 -