oj.uz

Submission #401424

# Submission time Handle Problem Language Result Execution time Memory
401424 2021-05-10T08:04:19 Z Hazem Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 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],n,m;
bool vis[N];

int dfs1(int i,int pre){

    int ret = 1;
    for(auto x:adj[i])
        if(x!=pre)
            ret += dfs1(x,i);

    return ret;
}

LL dfs(int i,int pre,int sz){

    vis[i] = sizes[i] = 1;
    LL ret = 0;
    for(auto x:adj[i])
        if(x!=pre){
            ret += dfs(x,i,sz);
            sizes[i] += sizes[x];
        }

    LL cur = sz-1;
    for(auto x:adj[i]){
        LL v = 0;
        if(x==pre)v = sz-sizes[i];
        else v = sizes[x];
        ret += (cur-v)*v;
    }

    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 'long long int dfs(int, int, int)':
count_triplets.cpp:33:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |     vis[i] = sizes[i] = 1;
      |              ~~~~~~~~~^~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:57:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   57 |     scanf("%d%d",&n,&m);
      |            ~^    ~~
      |             |    |
      |             int* long long int*
      |            %lld
count_triplets.cpp:57:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   57 |     scanf("%d%d",&n,&m);
      |              ~^     ~~
      |               |     |
      |               int*  long long int*
      |              %lld
count_triplets.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 551 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 551 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

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 4968 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 4 ms 5068 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4944 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 5068 KB Output is correct
14 Correct 4 ms 5064 KB Output is correct
15 Correct 4 ms 5012 KB Output is correct
16 Correct 4 ms 4940 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 5024 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 59 ms 9004 KB Output is correct
2 Correct 60 ms 9048 KB Output is correct
3 Correct 60 ms 9088 KB Output is correct
4 Correct 60 ms 9028 KB Output is correct
5 Correct 61 ms 9064 KB Output is correct
6 Correct 75 ms 14020 KB Output is correct
7 Correct 70 ms 12312 KB Output is correct
8 Correct 72 ms 11592 KB Output is correct
9 Correct 67 ms 10620 KB Output is correct
10 Correct 69 ms 9100 KB Output is correct
11 Correct 62 ms 10268 KB Output is correct
12 Correct 60 ms 10308 KB Output is correct
13 Correct 61 ms 10340 KB Output is correct
14 Correct 70 ms 10028 KB Output is correct
15 Correct 46 ms 9880 KB Output is correct
16 Correct 32 ms 8772 KB Output is correct
17 Correct 43 ms 10640 KB Output is correct
18 Correct 44 ms 10556 KB Output is correct
19 Correct 42 ms 10640 KB Output is correct
20 Correct 46 ms 10564 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 Runtime error 646 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 9284 KB Output is correct
2 Correct 60 ms 9028 KB Output is correct
3 Runtime error 756 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 551 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 551 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -