Submission #259415

#	Time	Username	Problem	Language	Result	Execution time	Memory
259415		Kastanda	Duathlon (APIO18_duathlon)	C++11	100 / 100	151 ms	31736 KiB

count_triplets

// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005 * 2;
int n, m, ts, nwn, H[N], MN[N], M[N], C[N], SZ[N]; ll tot;
vector < int > Bcc, Adj[N], Ad[N];
void DFS(int v, int p)
{
        nwn ++;
        M[v] = C[v] = 1;
        MN[v] = H[v];
        for (int u : Adj[v])
                if (u != p)
                {
                        if (!M[u])
                        {
                                int i = (int)Bcc.size();
                                H[u] = H[v] + 1;
                                DFS(u, v);
                                MN[v] = min(MN[v], MN[u]);
                                if (MN[u] >= H[v])
                                {
                                        ++ ts;
                                        while (Bcc.size() > i)
                                                Ad[Bcc.back()].push_back(ts),
                                                Ad[ts].push_back(Bcc.back()),
                                                Bcc.pop_back();
                                        Ad[v].push_back(ts);
                                        Ad[ts].push_back(v);
                                        C[ts] = (int)Ad[ts].size() - 2;
                                }
                        }
                        else
                                MN[v] = min(MN[v], H[u]);
                }
        Bcc.push_back(v);
}
void DFS2(int v, int p)
{
        SZ[v] = v <= n;
        ll Cnt = (ll)nwn * (nwn - 1);
        for (int u : Ad[v])
                if (u != p)
                        DFS2(u, v), Cnt -= (ll)SZ[u] * (SZ[u] - 1), SZ[v] += SZ[u];
        Cnt -= (ll)(nwn - SZ[v]) * (nwn - SZ[v] - 1);
        tot += (ll)Cnt * C[v];
}
int main()
{
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i ++)
        {
                int v, u;
                scanf("%d%d", &v, &u);
                Adj[v].push_back(u);
                Adj[u].push_back(v);
        }
        ts = n;
        for (int i = 1; i <= n; i ++)
                if (!M[i])
                {
                        nwn = 0;
                        DFS(i, 0);
                        Bcc.clear();
                        DFS2(i, 0);
                        tot -= (ll)nwn * (nwn - 1) * 2LL;
                }
        return !printf("%lld\n", tot);
}

Compilation message (stderr)

count_triplets.cpp: In function 'void DFS(int, int)':
count_triplets.cpp:25:59: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                                         while (Bcc.size() > i)
                                                ~~~~~~~~~~~^~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:51:14: 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:55:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &v, &u);
                 ~~~~~^~~~~~~~~~~~~~~~

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