Submission #49640

#	Time	Username	Problem	Language	Result	Execution time	Memory
49640		gs13105	Duathlon (APIO18_duathlon)	C++17	100 / 100	275 ms	30672 KiB

count_triplets

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

const int MAXN = 100000;

vector<int> arr[MAXN + 10];
int dis[MAXN + 10];
int low[MAXN + 10];
int tim;

vector<int> bcc[MAXN + 10];
vector<int> cmp[MAXN + 10];
int siz;

int cur;

void f(int x, int p)
{
    cur++;
    dis[x] = ++tim;
    low[x] = dis[x];

    for(int &y : arr[x])
    {
        if(y == p)
            continue;

        if(!dis[y])
        {
            f(y, x);
            low[x] = min(low[x], low[y]);
        }
        else
            low[x] = min(low[x], dis[y]);
    }
}

void color(int x, int c)
{
    if(c)
    {
        bcc[c].push_back(x);
        cmp[x].push_back(c);
    }
    for(auto &i : arr[x])
    {
        if(cmp[i].size())
            continue;
        if(low[i] >= dis[x])
        {
            bcc[++siz].push_back(x);
            cmp[x].push_back(siz);
            color(i, siz);
        }
        else
            color(i, c);
    }
}

int cnt[MAXN + 10];

long long g(int c, int p)
{
    long long r = 0;
    long long t = 0;
    for(int x : bcc[c])
    {
        if(x == p)
        {
            cnt[c]++;
            continue;
        }

        int sum = 1;
        for(int d : cmp[x])
        {
            if(d == c)
                continue;

            r += g(d, x);
            sum += cnt[d] - 1;
        }
        cnt[c] += sum;
        t += 1LL * sum * (sum - 1);
    }

    if(p)
    {
        int tmp = cur - cnt[c] + 1;
        t += 1LL * tmp * (tmp - 1);
    }

    r += ((int)bcc[c].size() - 1) * t;
    return r;
}

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n, m, i;
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        arr[x].push_back(y);
        arr[y].push_back(x);
    }

    long long r = 0;
    for(i = 1; i <= n; i++)
    {
        if(dis[i])
            continue;

        cur = 0;
        f(i, 0);
        color(i, 0);

        if(cur < 3)
            continue;

        long long t = g(siz, 0);
        int sz = cur;
        r += 1LL * sz * (sz - 1) * (sz - 2) - t;
    }

    printf("%lld", r);
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:119: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:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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