Submission #1285202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285202		StefanSebez	Duathlon (APIO18_duathlon)	C++17	100 / 100	84 ms	37020 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2e5+50;
mt19937 rng(time(0));
bool test=false;
vector<int>E[N];
ll n,m;
int low[N],disc[N],tajm;
vector<int>stek;
vector<int>E1[N];
int n1;
void Tarjan(int u){
    disc[u]=low[u]=++tajm;
    stek.pb(u);
    for(auto i:E[u]){
        if(disc[i]==0){
            Tarjan(i),low[u]=min(low[u],low[i]);
            if(low[i]>=disc[u]){
                n1++;
                while(!stek.empty()&&disc[stek.back()]>=disc[i]){
                    int v=stek.back();stek.pop_back();
                    E1[n1].pb(v);
                }
                E1[u].pb(n1);
            }
        }
        else low[u]=min(low[u],disc[i]);
    }
}
ll sz[N];
void DFSsetup(int u,int p=0){
    if(u<=n)sz[u]=1;
    for(auto i:E1[u])if(i!=p){
        DFSsetup(i,u);
        sz[u]+=sz[i];
    }
}
ll DFS(int u,int rt,int p=0){
    ll res=0;
    vector<ll>d={sz[rt]-sz[u]};
    for(auto i:E1[u])if(i!=p){
        res+=DFS(i,rt,u);
        if(u>n)res+=sz[i]*(sz[i]-1)*E1[u].size();
    }
    if(u>n)res+=(sz[rt]-sz[u])*(sz[rt]-sz[u]-1)*E1[u].size();
    return res;
}
ll Solve(){
    ll res=0;vector<int>roots;
    n1=n;
    for(int i=1;i<=n;i++){if(disc[i]==0) Tarjan(i),roots.pb(i);}
    for(auto i:roots){
        DFSsetup(i);
        ll x=DFS(i,i);
        res+=(sz[i]*(sz[i]-1)*(sz[i]-2))-x;
    }
    return res;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v);E[v].pb(u);
    }
    printf("%lld\n",Solve());
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:68:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~

• 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