oj.uz

Submission #232867

# Submission time Handle Problem Language Result Execution time Memory
232867 2020-05-18T12:34:05 Z Ruxandra985 Duathlon (APIO18_duathlon) C++14
0 / 100
 142 ms 33224 KB 
#include <bits/stdc++.h>
#define DIMN 100005
#define DIMM 200005
using namespace std;
int low[DIMN] , bicnx , lvl[DIMN] , taken[DIMN] , f[DIMN] , two[DIMN] , under[DIMN];
stack <int> st;
vector <int> v[DIMN] , w[2 * DIMN];
set <int> sol[DIMN];
int x , n , val;
void dfs_bic (int nod,int tt){
    int 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 (int nod){

    int sum , i , vecin , tata=0;

    //printf ("%d ",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();

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

    }
    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];
            two[nod] += two[vecin];

        }
        else tata = vecin;

    }

    two[nod] = under[nod] * (under[nod] - 1)/2;

    //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 + 2 * (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];
                val = val + 2 * x * ( two[vecin] - under[vecin] );
                if (x >= 2){
                    val = val + 2 * x * (x - 1) * ( under[vecin] - 1 );
                }

            }

        }


    }

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

}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int m , i , x , y , nod;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&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 <int> :: 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);

        }

    }
    fprintf (fout,"%d",val);
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs_bic(int, 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(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:84:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < w[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
count_triplets.cpp:110: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:139:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:141:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 28664 KB Output isn't correct
2 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 142 ms 33224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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