Submission #128358

#	Time	Username	Problem	Language	Result	Execution time	Memory
128358		shafinalam	Duathlon (APIO18_duathlon)	C++14	23 / 100	1141 ms	1048580 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
const int mxn = 1e5+5;
typedef long long ll;
vector<int>adj[mxn];
ll sub[mxn];
bool vis[mxn];
ll ans = 0;

void dfs1(int u, int p)
{
    sub[u] = 1;
    vis[u] = 1;
    for(auto v : adj[u])
    {
        if(v==p) continue;
        dfs1(v, u);
        sub[u]+=sub[v];
    }
}
void dfs2(int u, int p, int root)
{
    ans+=((sub[root]-sub[u])*(sub[u]-1)*2);
    for(auto v : adj[u])
    {
        if(v==p) continue;
        dfs2(v, u, root);
        ans+=((sub[u]-sub[v]-1)*sub[v]);
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            dfs1(i, i);
            dfs2(i, i, i);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

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