oj.uz

Submission #233074

# Submission time Handle Problem Language Result Execution time Memory
233074 2020-05-19T08:34:44 Z Ruxandra985 Duathlon (APIO18_duathlon) C++14
0 / 100
 154 ms 36436 KB 
#include <bits/stdc++.h>
#define DIMN 100005
#define DIMM 200005
using namespace std;
long long low[DIMN] , bicnx , lvl[DIMN] , taken[DIMN] , f[DIMN] , two[DIMN] , under[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 dfs (long long nod){

    long long sum , i , vecin , tata=0;

    //prlong longf ("%lld ",nod);

    f[nod] = 1;
    sum = 0;
    if (nod > n){ /// nod

        under[nod] = 1;
        two[nod] = 0;

    }
    else { /// componenta
        under[nod] = sol[bicnx - nod + 1].size();

        two[nod] = 0;

    }
    for (i = 0 ; i < w[nod].size() ; i++){

        vecin = w[nod][i];
        if (!f[vecin]){
            dfs(vecin);

            under[nod] += under[vecin] - 1;
            sum += under[vecin];

            //if (nod > n)
            two[nod] += two[vecin];

        }
        else tata = vecin;

    }

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

        x = sol[bicnx - nod + 1].size();
        two[nod] += x * (x - 1) / 2;
        two[nod] += (x - w[nod].size()) * (x - w[nod].size() - 1) / 2;
        /// alegi 2 noduri ne-critice in orice ordine

        /// pe de alta pt, pot sa iau un nod din comp de aici si un nod
        /// din una de jos

        two[nod] += (x - 1) * (under[nod] - x);


    }


    //if (nod == 1)
      //  printf ("a");
    if (nod > n){ /// nod

        sum = under[nod];

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

            vecin = w[nod][i];
            if (vecin != tata){

                val = val + (under[vecin] - 1) * (sum - under[vecin]);

                if (under[vecin] - 1 >= 2){

                    val = val + 2 * (two[vecin] - (under[vecin] - 1)) * (sum - under[vecin]);

                }

                //val = val + two[vecin] - under[vecin] + 1;

            }

        }


    }
    else { /// componenta

        if (sol[bicnx - nod + 1].size() >= 3){

            x = sol[bicnx - nod + 1].size();
            val = val + x * (x - 1) * (x - 2);
            /// iei 3 din aceeasi comp, CU noduri critice!!!

        }

        x = sol[bicnx - nod + 1].size();

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

            vecin = w[nod][i];
            if (vecin != tata){
                /// din subarborele lui vecin iau 2, din alt subarbore iau unul

                val = val + 2 * (sum - under[vecin]) * two[vecin];

                /// iau 1 din nodul curent si doua de sub

                val = val + 2 * (x - 1) * ( two[vecin] - under[vecin] + 1 );
                if (x >= 2){

                    val = val + 2 * (x - 1) * (x - 2) * (under[vecin] - 1);

                    val = val + 2 * (x - 1) * (under[vecin] - 1);
                }

            }

        }


    }

    //printf ("%lld %lld\n" , nod , val);

}


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);

        }

    }

    /// taken[nod] > 1 => nod critic


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

        for (set <long long> :: iterator it = sol[i].begin() ; it != sol[i].end() ; it++){
            nod = *it;
            nod += n;
            if (taken[nod - n] > 1){
                w[nod].push_back(bicnx - i + 1);

                w[bicnx - i + 1].push_back(nod);

            }

        }

    }

    /// w e arborele componentelor biconexe
    /// sau sunt mai multi arbori daca graful nu era conex

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

        if (!f[i]){

            dfs (i);

        }

    }
    //dfs(1);
    fprintf (fout,"%lld",val);
    return 0;
}

Compilation message

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 dfs(long long int)':
count_triplets.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < w[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < w[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
count_triplets.cpp:132: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:167: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:169: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12032 KB Output is correct
5 Correct 13 ms 12032 KB Output is correct
6 Correct 11 ms 12032 KB Output is correct
7 Correct 12 ms 12160 KB Output is correct
8 Correct 11 ms 12032 KB Output is correct
9 Correct 11 ms 12032 KB Output is correct
10 Correct 11 ms 12032 KB Output is correct
11 Incorrect 11 ms 12032 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12032 KB Output is correct
5 Correct 13 ms 12032 KB Output is correct
6 Correct 11 ms 12032 KB Output is correct
7 Correct 12 ms 12160 KB Output is correct
8 Correct 11 ms 12032 KB Output is correct
9 Correct 11 ms 12032 KB Output is correct
10 Correct 11 ms 12032 KB Output is correct
11 Incorrect 11 ms 12032 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 29792 KB Output is correct
2 Correct 136 ms 29816 KB Output is correct
3 Incorrect 142 ms 33400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 12288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 36384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 12288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 36436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12032 KB Output is correct
5 Correct 13 ms 12032 KB Output is correct
6 Correct 11 ms 12032 KB Output is correct
7 Correct 12 ms 12160 KB Output is correct
8 Correct 11 ms 12032 KB Output is correct
9 Correct 11 ms 12032 KB Output is correct
10 Correct 11 ms 12032 KB Output is correct
11 Incorrect 11 ms 12032 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12032 KB Output is correct
5 Correct 13 ms 12032 KB Output is correct
6 Correct 11 ms 12032 KB Output is correct
7 Correct 12 ms 12160 KB Output is correct
8 Correct 11 ms 12032 KB Output is correct
9 Correct 11 ms 12032 KB Output is correct
10 Correct 11 ms 12032 KB Output is correct
11 Incorrect 11 ms 12032 KB Output isn't correct
12 Halted 0 ms 0 KB -