Submission #771738

#	Time	Username	Problem	Language	Result	Execution time	Memory
771738		davitmarg	Duathlon (APIO18_duathlon)	C++17	8 / 100	50 ms	21452 KiB

count_triplets

/*
DavitMarg
In pr honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 500005;

LL n, m;
vector<int> g[N];
int used[N], color, path_type[N];
LL sz[N];

void dfs(int v)
{
    used[v] = color;
    if (g[v].size() == 1)
        path_type[color] = 1;
    sz[color]++;

    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if (used[to])
            continue;
        dfs(to);
    }
}

void subtask3()
{
    for(int i = 1; i<=n;i++)
        if (!used[i])
        {
            color++;
            dfs(i);
        }

    LL ans = 0;

    for (int i = 1; i <= color; i++)
    {
        LL cnt = sz[i] * (sz[i] - 1ll) * (sz[i] - 2ll);
        if (path_type[i] == 1)
            ans += cnt / 3ll;
        else
            ans += cnt;
    }

    cout << ans << endl;
    exit(0);
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int mx_deg = 0;
    for(int i = 1; i <= n;i++)
		mx_deg = max(mx_deg, (int)g[i].size());

    if(mx_deg <= 2)
        subtask3();

}

int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*


*/

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < g[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~

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