Submission #252700

#	Time	Username	Problem	Language	Result	Execution time	Memory
252700		Sugardorj	Duathlon (APIO18_duathlon)	C++14	8 / 100	140 ms	15984 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
long long b[323567],c[323456],a[323456],tt,d[334564],e[456744];
long long x,m,n,t,k,l;
long long i , j,r,s,y,z;
vector <long long> p[345678],q;
void dfs(long long x){
    c[x] = 1;
    t++;
    if (p[x].size()==1)
        y=1;
    for(auto u:p[x]){
        if (c[u])
            continue;
        dfs(u);
    }
}
int main(){
    cin >> n>>m;
    for (i = 0; i<m; i ++){
        cin >> x>>y;
        p[x].push_back(y);
        p[y].push_back(x);   
    }
    s=0;
    for (i = 1; i <=n; i ++){
        if (c[i])
            continue;
        t=0;
        y=0;
        dfs(i);
        l = t*(t-1)*(t-2);
        if (y==1)
            l/=3;
        s+=l;
    }
    cout << s;
}

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