Submission #569081

#	Time	Username	Problem	Language	Result	Execution time	Memory
569081		Waratpp123	Duathlon (APIO18_duathlon)	C++14	23 / 100	1103 ms	1048576 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
vector<long long> g[100010];
long long ans=0,sz[100010],n,gr[100010],cnt=0;
unordered_map<long long,long long> mp[100010];
void findsz(long long i,long long p){
    gr[i]=cnt;
    for(auto x: g[i]){
        if(x==p) continue;
        findsz(x,i);
    }
    sz[i]++;
    for(auto x: g[i]){
        if(x==p) continue;
        sz[i]+=sz[x];
    }
}
void findans(long long i,long long p,long long r){
    long long sum=sz[r]-sz[i];
    ans-=((sz[r]-sz[i])*(sz[r]-sz[i]));
    for(auto x : g[i]){
        if(x==p) continue;
        sum+=sz[x];
        ans-=(sz[x]*sz[x]);
    }
    ans+=(sum*sum);
    for(auto x : g[i]){
        if(x==p) continue;
        findans(x,i,r);
    }
}
int main(){
    long long m,u,v,i;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%lld %lld",&u,&v);
        if(mp[u][v]!=0) continue;
        mp[u][v]=mp[v][u]=1;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(i=1;i<=n;i++){
        if(gr[i]!=0) continue;
        cnt++;
        findsz(i,-1);
        findans(i,-1,i);
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

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

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