Submission #982324

#	Time	Username	Problem	Language	Result	Execution time	Memory
982324		Ghulam_Junaid	Duathlon (APIO18_duathlon)	C++17	5 / 100	1040 ms	396 KiB

count_triplets

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

const int N = 55;
int n, m;
vector<int> g[N];
bool vis[N];

void dfs(int v){
    if (vis[v]) return;
    vis[v] = 1;
    for (int u : g[v])
        if (!vis[u])
            dfs(u);
}

int main(){
    cin >> n >> m;

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

    int ans = 0;
    for (int s = 1; s <= n; s ++){
        for (int c = 1; c <= n; c ++){
            for (int f = 1; f <= n; f ++){
                if (s == c or s == f or c == f) continue;

                bool good = 1;
                for (int e = 1; e <= n; e ++){
                    if (e == c) continue;

                    memset(vis, 0, sizeof vis);
                    vis[e] = 1;
                    dfs(s);

                    if (vis[c]) continue;

                    vis[e] = 1;
                    dfs(f);

                    if (vis[c]) continue;
                    
                    good = 0;
                    break;
                }

                ans += good;
            }
        }
    }

    cout << ans << endl;
}

/*

There is some vertex mid i.e every path from c to f and c to s goes through it.
if there is no such vertex then (s, c, f) is a valid tuple.

*/

• 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