Submission #111220

#	Time	Username	Problem	Language	Result	Execution time	Memory
111220		SamAnd	Duathlon (APIO18_duathlon)	C++17	66 / 100	544 ms	44924 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];
vector<int> gg[N];

int px[N];
int pp[N];
int q[N];
void dfs03(int x, int p, int u)
{
    pp[x] = u;
    q[x] = v[x].size();
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        px[h] = gg[x][i];
        dfs03(h, x, u);
        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]);
        gg[c[(*it).first]].push_back((*it).first);
        t[(*it).first].push_back((*it).second);
    }

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

    for (int i = 1; i <= k; ++i)
    {
        if (!pp[i])
            dfs03(i, i, i);
    }

    for (int i = 1; i <= k; ++i)
    {
        long long ysum = 0;
        vector<long long> sum;
        sum.assign(v[i].size(), 0);
        for (int j = 0; j < v[i].size(); ++j)
        {
            int x = v[i][j];
            for (int k = 0; k < t[x].size(); ++k)
            {
                int y = t[x][k];
                if (y != px[i])
                    sum[j] += q[c[y]];
                else
                    sum[j] += (q[pp[i]] - q[i]);
            }
            for (int k = 0; k < t[x].size(); ++k)
            {
                int y = t[x][k];
                if (y != px[i])
                {
                    sum[j] -= q[c[y]];
                    ans += (sum[j] * q[c[y]]);
                    sum[j] += q[c[y]];
                }
                else
                {
                    sum[j] -= (q[pp[i]] - q[i]);
                    ans += (sum[j] * (q[pp[i]] - q[i]));
                    sum[j] += (q[pp[i]] - q[i]);
                }
            }
            sum[j]++;
            ysum += sum[j];
        }
        long long yysum = 0;
        for (int j = 0; j < v[i].size(); ++j)
        {
            ysum -= sum[j];
            ans += ((sum[j] - 1) * ysum) * 2;
            yysum += (sum[j] * ysum);
            ysum += sum[j];
        }
        for (int j = 0; j < v[i].size(); ++j)
        {
            ysum -= sum[j];
            yysum -= (sum[j] * ysum) * 2;
            ans += yysum;
            yysum += (sum[j] * ysum) * 2;
            ysum += sum[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, int)':
count_triplets.cpp:81: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:138:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
count_triplets.cpp:141:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k < t[x].size(); ++k)
                             ~~^~~~~~~~~~~~~
count_triplets.cpp:149:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k < t[x].size(); ++k)
                             ~~^~~~~~~~~~~~~
count_triplets.cpp:169:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
count_triplets.cpp:176:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~

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