Submission #54192

#	Time	Username	Problem	Language	Result	Execution time	Memory
54192		bogdan10bos	Duathlon (APIO18_duathlon)	C++14	31 / 100	331 ms	58108 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

int N, M;

namespace Biconnex
{
    int h[400005], low[400005];
    vector<int> edg[400005];
    stack<int> stv;

    int K = 0;
    vector<int> bcx[400005], cmp[400005];

    void addEdge(int x, int y)
    {
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    void DFS(int nod, int fth = 0)
    {
        h[nod] = h[fth] + 1;
        low[nod] = h[nod];
        stv.push(nod);
        for(auto nxt: edg[nod])
        {
            if(nxt == fth)  continue;
            if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; }

            stv.push(nod);
            DFS(nxt, nod);
            low[nod] = min(low[nod], low[nxt]);
            if(low[nxt] >= h[nod])
            {
                K++;
                while(stv.top() != nod)
                {
                    int x = stv.top();
                    cmp[K].push_back(x);
                    bcx[x].push_back(K);
                    stv.pop();
                }
                cmp[K].push_back(nod);
                bcx[nod].push_back(K);
                stv.pop();
            }
        }
    }

    void getbiconnex()
    {
        for(int i = 1; i <= N; i++)
            if(!h[i])
                DFS(i);

        for(int i = 1; i <= K; i++)
            cmp[i].erase(unique(cmp[i].begin(), cmp[i].end()), cmp[i].end());
        for(int i = 1; i <= N; i++)
            bcx[i].erase(unique(bcx[i].begin(), bcx[i].end()), bcx[i].end());
    }
}

namespace Tree
{
    int N, K;
    LL ans;
    int f[400005], viz[400005];
    int valuare[400005], val[400005], sz[400005], cmp[400005];
    vector<int> edg[400005];

    void addEdge(int x, int y)
    {
        f[x] = f[y] = 1;
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    void setValue(int x, int y) { f[x] = 1; val[x] = y; }

    void DFS(int nod, int fth = 0)
    {
        if(fth == 0)    cmp[nod] = nod;
        else    cmp[nod] = cmp[fth];
        viz[nod] = 1;
        valuare[nod] = val[nod] == -1 ? 1 : val[nod] - edg[nod].size();
        sz[nod] = valuare[nod];
        for(auto nxt: edg[nod])
        {
            if(nxt == fth)  continue;

            DFS(nxt, nod);
            sz[nod] += sz[nxt];
        }
    }

    void solve()
    {
        ans = 0;

        for(int i = 1; i <= N; i++)
            if(f[i])
                setValue(i, -1);

        for(int i = 1; i <= N + K; i++)
            if(f[i] && !viz[i])
                DFS(i);

        for(int i = N + 1; i <= N + K; i++)
            if(f[i])
            {
                int nod = i;
                int M = sz[ cmp[i] ];

                /// 3 elemente
                ans += 1LL * val[i] * (val[i] - 1) * (val[i] - 2);

                /// 2 elemente
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[nod])   continue;
                    ans += 2LL * (val[i] - 1) * (val[i] - 1) * (sz[nxt] - 1);
                }
                if(sz[nod] != M)
                {
                    ans += 2LL * (val[i] - 1) * (val[i] - 1) * (M - sz[nod] - 1);
                }

                /// 1 element (mijloc)
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[nod])   continue;
                    ans += 1LL * val[i] * (sz[nxt] - 1) * (M - val[i] - sz[nxt] + 1);
                }
                if(sz[nod] != M)
                {
                    ans += 1LL * val[i] * (M - sz[nod] - 1) * (sz[nod] - val[nod] + 1);
                }
            }

        for(int i = 1; i <= N; i++)
            if(f[i])
            {
                bool ok = true;
                for(auto nxt: edg[i])
                    if(nxt > N) ok = false;
                if(!ok)
                {
                    int cnt = 0;
                    for(auto nxt: edg[i])
                        if(val[nxt] > 0)
                            cnt += val[nxt] - 1;
                    for(auto nxt: edg[i])
                        if(val[nxt] > 0)
                            ans -= 1LL * (val[nxt] - 1) * (cnt - val[nxt] + 1);
                    continue;
                }

                int M = sz[ cmp[i] ];
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[i]) continue;
                    ans += 1LL * sz[nxt] * (M - sz[nxt] - 1);
                }
                if(sz[i] != M)
                    ans += 1LL * (sz[i] - 1) * (M - sz[i]);
            }

        printf("%lld\n", ans);
    }
}

void makeTree()
{
    using namespace Biconnex;
    for(int i = 1; i <= K; i++)
    {
        if(cmp[i].size() > 2)
        {
            Tree::setValue(i + N, cmp[i].size());
            for(auto &nod: cmp[i])
                if(bcx[nod].size() > 1)
                    Tree::addEdge(i + N, nod);
        }
        else
        {
            Tree::addEdge(cmp[i][0], cmp[i][1]);
        }
    }
    Tree::N = N;
    Tree::K = K;
}

void gen()
{
    freopen("1.in", "w", stdout);
    int N = 1e5;
    printf("%d %d\n", N, N);
    for(int i = 1; i < N; i++)
        printf("%d %d\n", i, i + 1);
    printf("%d %d\n", 1, N);
    exit(0);
}

int main()
{
    //gen();

    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        Biconnex::addEdge(x, y);
    }

    Biconnex::getbiconnex();

    makeTree();

    Tree::solve();

    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void gen()':
count_triplets.cpp:201:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("1.in", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:219: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:223: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: 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