Submission #111218

#	Time	Username	Problem	Language	Result	Execution time	Memory
111218		SamAnd	Duathlon (APIO18_duathlon)	C++17	25 / 100	1075 ms	33936 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005;

int n, m;
vector<int> a[N];

long long ans;

int c[N];
int tin[N], ti;
int fup[N];
set<pair<int, int> > s;
void dfs0(int x, int p)
{
    c[x] = 1;
    fup[x] = tin[x] = ti++;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        if (c[h])
        {
            fup[x] = min(fup[x], tin[h]);
        }
        else
        {
            dfs0(h, x);
            if (tin[x] < fup[h])
            {
                s.insert(m_p(x, h));
                s.insert(m_p(h, x));
            }
            fup[x] = min(fup[x], fup[h]);
        }
    }
}

int k;
void dfs01(int x)
{
    c[x] = k;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (s.find(m_p(x, h)) != s.end())
            continue;
        if (!c[h])
            dfs01(h);
    }
}

int cc[N];
int kk;
void dfs02(int x)
{
    cc[x] = kk;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (!cc[h])
            dfs02(h);
    }
}

vector<int> v[N];

vector<int> t[N];
vector<int> g[N];

int q[N];
void dfs03(int x, int p)
{
    q[x] = v[x].size();
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs03(h, x);
        q[x] += q[h];
    }
}

void solv0()
{
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
            dfs0(i, i);
    }
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
        {
            ++k;
            dfs01(i);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!cc[i])
        {
            ++kk;
            dfs02(i);
        }
    }

    for (set<pair<int, int> >::iterator it = s.begin(); it != s.end(); ++it)
    {
        g[c[(*it).first]].push_back(c[(*it).second]);
        t[(*it).first].push_back((*it).second);
    }

    for (int i = 1; i <= n; ++i)
        v[c[i]].push_back(i);

    for (int m = 1; m <= n; ++m)
    {
        dfs03(c[m], c[m]);

        long long sum = 0;
        for (int i = 0; i < t[m].size(); ++i)
        {
            int h = t[m][i];
            sum += q[c[h]];
        }
        for (int i = 0; i < t[m].size(); ++i)
        {
            int h = t[m][i];
            sum -= q[c[h]];
            ans += (sum * q[c[h]]);
            sum += q[c[h]];
        }

        vector<long long> ysum;
        ysum.assign(v[c[m]].size(), 1);

        for (int i = 0; i < v[c[m]].size(); ++i)
        {
            int x = v[c[m]][i];

            if (x == m)
                continue;

            for (int j = 0; j < t[x].size(); ++j)
            {
                int h = t[x][j];
                ysum[i] += q[c[h]];
            }

            ans += (sum * ysum[i] * 2);
        }

        for (int i = 0; i < v[c[m]].size(); ++i)
        {
            int x = v[c[m]][i];
            if (x == m)
                continue;
            for (int j = 0; j < v[c[m]].size(); ++j)
            {
                int y = v[c[m]][j];
                if (y == m || y == x)
                    continue;
                ans += (ysum[i] * ysum[j]);
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    solv0();
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs0(int, int)':
count_triplets.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs01(int)':
count_triplets.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs02(int)':
count_triplets.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs03(int, int)':
count_triplets.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void solv0()':
count_triplets.cpp:126:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < t[m].size(); ++i)
                         ~~^~~~~~~~~~~~~
count_triplets.cpp:131:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < t[m].size(); ++i)
                         ~~^~~~~~~~~~~~~
count_triplets.cpp:142:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v[c[m]].size(); ++i)
                         ~~^~~~~~~~~~~~~~~~
count_triplets.cpp:149:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < t[x].size(); ++j)
                             ~~^~~~~~~~~~~~~
count_triplets.cpp:158:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v[c[m]].size(); ++i)
                         ~~^~~~~~~~~~~~~~~~
count_triplets.cpp:163:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < v[c[m]].size(); ++j)
                             ~~^~~~~~~~~~~~~~~~

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