Submission #233312

#	Time	Username	Problem	Language	Result	Execution time	Memory
233312		Ruxandra985	Duathlon (APIO18_duathlon)	C++14	100 / 100	246 ms	55288 KiB

count_triplets

#include <bits/stdc++.h>
#define DIMN 200005
#define DIMM 200005
using namespace std;
long long low[DIMN] , bicnx , lvl[DIMN] , taken[DIMN] , f[DIMN] , under[DIMN] , two[DIMN];
stack <long long> st;
vector <long long> v[DIMN] , w[2 * DIMN];
set <long long> sol[DIMN];
long long x , n , val;
void dfs_bic (long long nod,long long tt){
    long long i,vecin;
    low[nod]=lvl[nod];
    st.push(nod);
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (vecin==tt)
            continue;
        if (lvl[vecin]==0){
            lvl[vecin]=1+lvl[nod];
            dfs_bic(vecin,nod);
            low[nod]=min(low[nod],low[vecin]);
            if (low[vecin]>=lvl[nod]){ /// nod e un nod critic
                bicnx++;
                do{
                    x=st.top();
                    taken[x]++;
                    st.pop();
                    sol[bicnx].insert(x);
                }
                while (x!=vecin);
                sol[bicnx].insert(nod);
                taken[nod]++;
                /// am scos din stiva muchiile care sunt in subarborele nod->vecin
            }
        }
        else low[nod]=min(low[nod],lvl[vecin]);
    }
}


void precalc (long long nod , long long tt){

    long long i , vecin;

    if (nod <= n){ /// nod

        under[nod] = 1;

    }
    else under[nod] = 0;

    for (i = 0 ; i < w[nod].size() ; i++){
        vecin = w[nod][i];
        if (vecin != tt){

            precalc (vecin , nod);

            under[nod] += under[vecin];

            if (nod > n){
                two[nod] += under[vecin] * (under[vecin] - 1);
            }


        }
    }

}

void dfs (long long root , long long nod , long long tt){
    long long i , vecin;

    f[nod] = 1;

    for (i = 0 ; i < w[nod].size() ; i++){
        vecin = w[nod][i];
        if (vecin != tt){

            dfs (root , vecin , nod);

        }
    }

    //if (nod == 5)
      //  printf ("a");

    if (nod <= n){ /// nod

        for (i = 0 ; i < w[nod].size() ; i++){
            vecin = w[nod][i];
            if (vecin != tt){

                val -= two[vecin];

                /// din vecin -> nod -> din vecin

            }
        }

    }
    else { /// componenta

        for (i = 0 ; i < w[nod].size() ; i++){
            vecin = w[nod][i];
            if (vecin != tt){

                val -= two[nod] - under[vecin] * (under[vecin] - 1) + (under[root] - under[nod]) * (under[root] - under[nod] - 1);

            }
        }

    }


}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long m , i , x , y , nod;
    fscanf (fin,"%lld%lld",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%lld%lld",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (i = 1 ; i <= n ; i++){
        if (!lvl[i]){

            lvl[i] = 1;
            dfs_bic (i , 0);

        }

    }

    for (i = 1 ; i <= bicnx ; i++){

        for (set <long long> :: iterator it = sol[i].begin() ; it != sol[i].end() ; it++){

            nod = *it;

            w[nod].push_back(n + i);
            w[n + i].push_back(nod);

            //fprintf (fout,"%lld %lld\n" , nod , n + i);

        }

    }

    for (i = 1 ; i <= n ; i++){
        if (!f[i]){
            precalc(i , 0);
            dfs(i , i , 0);
            val += under[i] * (under[i] - 1) * (under[i] - 2);
        }
    }

    fprintf (fout,"%lld",val);

    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs_bic(long long int, long long int)':
count_triplets.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'void precalc(long long int, long long int)':
count_triplets.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < w[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(long long int, long long int, long long int)':
count_triplets.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < w[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp:89:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < w[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
count_triplets.cpp:103:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < w[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:122:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:124:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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