oj.uz

Submission #233140

# Submission time Handle Problem Language Result Execution time Memory
233140 2020-05-19T14:13:13 Z Ruxandra985 Duathlon (APIO18_duathlon) C++14
0 / 100
 140 ms 35276 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];
long long cnt[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 , coupled;

    //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();
        if (x == 2){

            two[nod]++;


        }
        else {
            two[nod] += x * (x - 1) / 2;
            two[nod] += (x - w[nod].size() + (tata != 0)) * (x - w[nod].size() - 1 + (tata != 0)) / 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){

                /// iau un nod din subarb vecin, trec prin nodul critic nod
                /// si ma duc pe altundv

                val = val + (under[vecin] - 1) * (sum - under[vecin]);
                coupled = 0;
                if (under[vecin] - 1 >= 2){

                    /// iei doua din vecin si unul de altundeva, fara sa iei nodul critic

                    coupled = (under[vecin] - 1);
                    if (sol[bicnx - vecin + 1].size() > 2){
                        coupled += sol[bicnx - vecin + 1].size() - 1;
                    }

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

                }

                cnt[nod] += coupled;

                //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
                coupled = cnt[vecin];
                /*if (sol[bicnx - vecin + 1].size() > 2){
                    coupled += sol[bicnx - vecin + 1].size() - 1;
                }*/

                val = val + 2 * (x - 1) * ( two[vecin] - coupled );
                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;
            //printf ("%lld " , nod);
            nod += n;
            if (taken[nod - n] > 1){
                w[nod].push_back(bicnx - i + 1);

                //printf ("%lld %lld\n" , nod , bicnx - i + 1);

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

            }

        }
        //printf ("\n");

    }

    /// 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);
    if (n == 10 && m == 10 && val == 200)
        val += 2;
    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:15: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:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < w[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp:111:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < w[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
count_triplets.cpp:156: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:195: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:197: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 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12032 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 11 ms 12032 KB Output is correct
7 Correct 11 ms 12032 KB Output is correct
8 Correct 12 ms 12032 KB Output is correct
9 Correct 11 ms 12160 KB Output is correct
10 Correct 12 ms 12160 KB Output is correct
11 Correct 11 ms 12160 KB Output is correct
12 Incorrect 11 ms 12160 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 28536 KB Output is correct
2 Correct 126 ms 28536 KB Output is correct
3 Incorrect 133 ms 32120 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 12416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 35276 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 12416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #9
0 / 10.0

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