Submission #1285151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285151		StefanSebez	Duathlon (APIO18_duathlon)	C++20	0 / 100	1133 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;
ll sajz[N];
void DFS(int u,int p,ll &res){
    sajz[u]=1;
    for(auto i:E[u]){
        if(i==p) continue;
        DFS(i,u,res);
        sajz[u]+=sajz[i];
    }
    res+=sajz[u]*(n-sajz[u]);
}
ll Stablo(){
    ll res=0;
    for(int i=0;i<=n;i++) sajz[i]=0;
    for(int i=1;i<=n;i++){
        if(sajz[i]!=0)continue;
        DFS(i,0,res);
        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:83:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   83 |                 printf("%i %i\n",n,m);
      |                         ~^       ~
      |                          |       |
      |                          int     long long int
      |                         %lli
count_triplets.cpp:83:29: warning: format '%i' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   83 |                 printf("%i %i\n",n,m);
      |                            ~^      ~
      |                             |      |
      |                             int    long long int
      |                            %lli
count_triplets.cpp:87:28: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   87 |                 printf("\n%i %i\n",x,y);
      |                           ~^       ~
      |                            |       |
      |                            int     long long int
      |                           %lli
count_triplets.cpp:87:31: warning: format '%i' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   87 |                 printf("\n%i %i\n",x,y);
      |                              ~^      ~
      |                               |      |
      |                               int    long long int
      |                              %lli
count_triplets.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld%lld",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:63:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |             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