Submission #603183

#	Time	Username	Problem	Language	Result	Execution time	Memory
603183		benjaminkleyn	Duathlon (APIO18_duathlon)	C++17	5 / 100	1093 ms	13580 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m;
vector<int> g[100000];
int par[100000];
bool vis[100000];
bool marked[100000];

void mark(int f)
{
    marked[f] = true;
    while (par[f] != f)
    {
        f = par[f];
        marked[f] = true;
    }
}

void dfs(int u, int f)
{
    if (u == f)
    {
        mark(f);
        return;
    }
    vis[u] = true;
    for (int v : g[u])
        if (!vis[v])
        {
            par[v] = u;
            dfs(v, f);
        }
    vis[u] = false;
}

int main()
{
    cin >> n >> m;
    for (int i = 0, u, v; i < m; i++)
    {
        cin >> u >> v;
        g[u-1].push_back(v-1);
        g[v-1].push_back(u-1);
    }

    ll res = 0;
    for (int s = 0; s < n; s++)
        for (int f = 0; f < n; f++)
        {
            if (s == f) continue;
            memset(vis, false, sizeof(vis));
            memset(marked, false, sizeof(marked));
            par[s] = s;
            dfs(s, f);
            for (int c = 0; c < n; c++)
                if (c != s && c != f && marked[c])
                    res++;

        }

    cout << res << '\n';

    return 0;
}

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