Submission #742133

#	Time	Username	Problem	Language	Result	Execution time	Memory
742133		speedyArda	Duathlon (APIO18_duathlon)	C++14	31 / 100	702 ms	1048576 KiB

count_triplets

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 1e5+5;
vector< vector<int> > adj(MAXN);
bool visited[MAXN];
long long sz[MAXN];
long long bgsz[MAXN];
int par[MAXN];
long long add[MAXN];
int n, m;
int find(int v)
{
    if(par[v] == v)
        return v;
    return par[v] = find(par[v]); 
}

void merge(int a, int b)
{
    a = find(a), b = find(b);
    if(a == b)
        return;
    if(bgsz[a] < bgsz[b])
        swap(a, b);
    par[b] = a;
    bgsz[a] += bgsz[b];
}
pair<long long, bool> subtask3(int v, int p)
{
    pair<long long, bool> ans = {1, false};
    visited[v] = true;

    for(int e : adj[v])
    {
        if(e == p)
            continue;
        if(visited[e]) {
            ans.second = true;
            continue;
        }
        pair<long long, bool> temp = subtask3(e, v);
        ans.first += temp.first;
        ans.second |= temp.second;
    }
    return ans;
}

long long subtask5(int v, int p)
{
    long long ans = 0;
    visited[v] = true;
    sz[v] = 1;
    long long chi_size = 0;
    for(int e : adj[v])
    {
        if(e == p)
            continue;
        ans += subtask5(e, v);
        sz[v] += sz[e];
        chi_size += sz[e];
    }
    int bigpar = find(v);
    long long par_size = bgsz[bigpar] - chi_size - 1;
    ans += par_size * chi_size;
    //cout << bgsz[bigpar] << "\n";
    for(int e : adj[v])
    {
        if(e == p)
            continue;
        ans += sz[e] * (bgsz[bigpar] - sz[e] - 1LL);
    }
    return ans;
}
int main() 
{
    long long temp = 0;
    add[0] = 0;
    for(long long i = 1; i < MAXN; i++)
    {
        temp += i;
        add[i] = add[i - 1] + temp;
        par[i] = i;
        bgsz[i] = 1;
    }
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int f, s;
        cin >> f >> s;
        adj[f].push_back(s);
        adj[s].push_back(f);
        merge(f, s);
    }

    int max_size = 0;
    for(int i = 1; i <= n; i++)
    {
        max_size = max(max_size, (int)adj[i].size());
    }
    long long ans = 0;
    if(max_size <= 2) // Subtask 3
    {
        for(int i = 1; i <= n; i++)
        {
            if(visited[i])
                continue;
            pair<long long, bool> curr = subtask3(i, -1);
            if(curr.second)
            {
                ans += curr.first * (curr.first - 1) * (curr.first - 2);
            } else if(curr.first >= 3)
            {
                ans += add[curr.first - 2] * 2LL;
            }
        }   
    } else //Subtask 4, 5
    {
        for(int i = 1; i <= n; i++)
        {
            if(visited[i])
                continue;
            ans += subtask5(i, -1);
        }
    }


    cout << ans << "\n";
    
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 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