Submission #1285179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285179		StefanSebez	Duathlon (APIO18_duathlon)	C++17	0 / 100	1136 ms	1114112 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]);
        else low[u]=min(low[u],disc[i]);
    }
    if(low[u]==disc[u]){
        n1++;
        while(stek.back()!=u){
            int v=stek.back();stek.pop_back();
            E1[n1].pb(v);
        }
        E1[u].pb(n1);
    }
}
ll sz[N];
ll DFS(int u,int p=0){
    ll res=0;
    for(auto i:E[u])if(i!=p){
        res+=DFS(i,u);
        sz[u]+=sz[i];
    }
}
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) res+=DFS(i);
    return res;
}*/

ll sajz[N];vector<int>temp;
void DFS2(int u,int p=0){
    sajz[u]=1;temp.pb(u);
    for(auto i:E[u])if(i!=p){
        DFS2(i,u);
        sajz[u]+=sajz[i];
    }
}
ll Stablo(){
    //for(int i=1;i<=n;i++){printf("%i: ",i);for(auto j:E[i]) printf("%i ",j);printf("\n");}
    ll res=0;
    for(int i=0;i<=n;i++) sajz[i]=0;
    for(int i=1;i<=n;i++)if(sajz[i]==0){
        DFS2(i);
        for(auto u:temp) res+=sajz[u]*(sajz[i]-sajz[u]);
        temp.clear();
        res-=(sajz[i]*(sajz[i]-1))/2;
    }
    res*=2;
    return res;
}

bool was1[N];
void DFS1(int u){
    was1[u]=true;
    for(auto i:E[u])if(!was1[i])DFS1(i);
}
ll Bruteforce(){
    ll res=0;
    for(int s=1;s<=n;s++){
        for(int c=1;c<=n;c++)if(s!=c){
            for(int f=1;f<=n;f++)if(f!=s&&f!=c){
                bool moze=true;
                for(int u=1;u<=n;u++)if(u!=c){
                    for(int i=1;i<=n;i++) was1[i]=false;
                    was1[u]=true;
                    DFS1(c);
                    if((u==s||!was1[s])&&(u==f||!was1[f])) moze=false;
                }
                res+=moze;
            }
        }
    }
    return res;
}
int main(){
    if(!test){
        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",Bruteforce());
        printf("%lld\n",Stablo());
    }
    else{
        /*int CT=1;
        while(CT++){
            if(CT%1==0)cerr<<"radi\n";
            n=70,m=n-1;
            for(int i=0;i<=n;i++) E[i].clear();
            vector<pair<int,int>>edges;
            for(int i=2;i<=n;i++){
                int p=rng()%(i-1)+1;
                E[p].pb(i);E[i].pb(p);
                edges.pb({p,i});
            }
            ll x=Stablo(),y=Bruteforce();
            if(x!=y){
                printf("%i %i\n",n,m);
                for(auto [u,v]:edges){
                    printf("%i %i\n",u,v);
                }
                printf("\n%i %i\n",x,y);
                return 0;
            }
        }*/
    }
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 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