oj.uz

Submission #401469

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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5068 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 5068 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 98 ms 24756 KB Output is correct
2 Correct 101 ms 24568 KB Output is correct
3 Correct 123 ms 18400 KB Output is correct
4 Correct 107 ms 21420 KB Output is correct
5 Correct 96 ms 16244 KB Output is correct
6 Correct 120 ms 16312 KB Output is correct
7 Correct 97 ms 14544 KB Output is correct
8 Correct 101 ms 15608 KB Output is correct
9 Correct 98 ms 13380 KB Output is correct
10 Correct 121 ms 14532 KB Output is correct
11 Correct 61 ms 12088 KB Output is correct
12 Correct 65 ms 11972 KB Output is correct
13 Correct 57 ms 11996 KB Output is correct
14 Correct 53 ms 11808 KB Output is correct
15 Correct 44 ms 11460 KB Output is correct
16 Correct 56 ms 11480 KB Output is correct
17 Correct 6 ms 7116 KB Output is correct
18 Correct 6 ms 7120 KB Output is correct
19 Correct 6 ms 6988 KB Output is correct
20 Correct 7 ms 6992 KB Output is correct
21 Correct 7 ms 6988 KB Output is correct
22 Correct 6 ms 6988 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Correct 4 ms 5032 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5144 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 5 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 4 ms 5036 KB Output is correct
12 Correct 5 ms 5068 KB Output is correct
13 Correct 5 ms 5060 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5068 KB Output is correct
16 Correct 5 ms 5076 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 5 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 76 ms 10576 KB Output is correct
2 Correct 89 ms 10644 KB Output is correct
3 Correct 74 ms 10676 KB Output is correct
4 Correct 104 ms 10628 KB Output is correct
5 Correct 105 ms 10576 KB Output is correct
6 Correct 106 ms 17388 KB Output is correct
7 Correct 99 ms 15012 KB Output is correct
8 Correct 88 ms 13892 KB Output is correct
9 Correct 104 ms 12740 KB Output is correct
10 Correct 74 ms 10692 KB Output is correct
11 Correct 76 ms 10692 KB Output is correct
12 Correct 96 ms 10580 KB Output is correct
13 Correct 82 ms 10688 KB Output is correct
14 Correct 66 ms 10556 KB Output is correct
15 Correct 65 ms 10460 KB Output is correct
16 Correct 52 ms 9724 KB Output is correct
17 Correct 47 ms 10920 KB Output is correct
18 Correct 50 ms 10940 KB Output is correct
19 Correct 55 ms 11044 KB Output is correct
20 Correct 53 ms 10996 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 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 78 ms 10584 KB Output is correct
2 Correct 89 ms 10636 KB Output is correct
3 Incorrect 98 ms 12264 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 5068 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 5068 KB Output isn't correct
2 Halted 0 ms 0 KB -