Submission #401420

#	Time	Username	Problem	Language	Result	Execution time	Memory
401420		Hazem	Duathlon (APIO18_duathlon)	C++14	0 / 100	96 ms	14048 KiB

count_triplets

#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];

LL dfs(int i,int pre){

    vis[i] = sizes[i] = 1;
    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];
        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);
    assert(m==n-1);

    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])
            ans += dfs(i,i);

    printf("%lld",ans);
}   

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10