oj.uz

Submission #401459

# Submission time Handle Problem Language Result Execution time Memory
401459 2021-05-10T09:51:21 Z Hazem Duathlon (APIO18_duathlon) C++14
0 / 100
 1000 ms 16928 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;
        }
    }

        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++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(i!=j&&i!=k&&j!=k)
                    ans += check(i,j,k,i);

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

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 10 ms 5020 KB Output is correct
9 Correct 198 ms 4940 KB Output is correct
10 Execution timed out 1083 ms 5068 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 10 ms 5020 KB Output is correct
9 Correct 198 ms 4940 KB Output is correct
10 Execution timed out 1083 ms 5068 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 16928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 4940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 9304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 4940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 9224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 10 ms 5020 KB Output is correct
9 Correct 198 ms 4940 KB Output is correct
10 Execution timed out 1083 ms 5068 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 10 ms 5020 KB Output is correct
9 Correct 198 ms 4940 KB Output is correct
10 Execution timed out 1083 ms 5068 KB Time limit exceeded
11 Halted 0 ms 0 KB -