oj.uz

Submission #401411

# Submission time Handle Problem Language Result Execution time Memory
401411 2021-05-10T07:28:56 Z Hazem Duathlon (APIO18_duathlon) C++14
0 / 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;

LL dfs(int i,int pre){

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

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

    return ret;
}

int main(){

    //freopen("out.txt","w",stdout);

    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);        
    }

    printf("%lld\n",dfs(1,1)*2);
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 580 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 580 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 1125 ms 616688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
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 5008 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 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Incorrect 4 ms 4940 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10168 KB Output is correct
2 Correct 62 ms 10220 KB Output is correct
3 Correct 60 ms 10168 KB Output is correct
4 Correct 56 ms 10180 KB Output is correct
5 Correct 68 ms 10268 KB Output is correct
6 Correct 65 ms 15172 KB Output is correct
7 Correct 66 ms 13504 KB Output is correct
8 Correct 70 ms 12688 KB Output is correct
9 Correct 71 ms 11804 KB Output is correct
10 Incorrect 56 ms 10172 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 5008 KB Output is correct
3 Runtime error 660 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 59 ms 10252 KB Output is correct
2 Correct 56 ms 10116 KB Output is correct
3 Runtime error 783 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 580 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 580 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -