Submission #237967

#	Time	Username	Problem	Language	Result	Execution time	Memory
237967		Ruxandra985	Tropical Garden (IOI11_garden)	C++14	0 / 100	7 ms	3968 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define DIMN 150010
using namespace std;


int tt[2][DIMN] , f[2][DIMN] , cod[2][DIMN] , poz[2][DIMN] , len_cycle[2][DIMN];
int dist[2][DIMN] , far[2][DIMN];
int prm[DIMN] , doi[DIMN];
vector <int> v[DIMN];
deque <pair <int,int> > dq;

void step_back (int &state , int &curr){

    if (tt[state][curr] > 0){
        curr = tt[state][curr];
        state = 0;
    }
    else {
        curr = -tt[state][curr];
        state = 1;
    }

}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
    int i , curr , state , vecin , new_state , discovered , pc , old_state , old_curr;
    int dis , len , sol , j;

    p++;

    for (i = 0 ; i < m ; i++){
        r[i][0]++;
        r[i][1]++;
        v[r[i][0]].push_back(r[i][1]);
        v[r[i][1]].push_back(r[i][0]);
    }

    for (i = 1 ; i <= n ; i++){
        prm[i] = doi[i] = -1;
        cod[0][i] = cod[1][i] = 0;
        poz[0][i] = poz[1][i] = 0;
        tt[0][i] = tt[1][i] = 0;
        len_cycle[0][i] = len_cycle[1][i] = 0;
    }

    for (i = 0 ; i < m ; i++){

        if (prm[r[i][0]] == -1)
            prm[r[i][0]] = r[i][1];
        else if (doi[r[i][0]] == -1)
            doi[r[i][0]] = r[i][1];

        if (prm[r[i][1]] == -1)
            prm[r[i][1]] = r[i][0];
        else if (doi[r[i][1]] == -1)
            doi[r[i][1]] = r[i][0];
    }
    /// ----------------------------------------------------------------------

    dq.push_back(make_pair(0 , p));
    f[0][p] = 1;
    while (!dq.empty()){

        state = dq.front().first;
        curr = dq.front().second;
        dq.pop_front();

        for (i = 0 ; i < v[curr].size() ; i++){
            vecin = v[curr][i];
            if (prm[vecin] == curr && !f[0][vecin]){
                if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){
                    dist[0][vecin] = 1 + dist[state][curr];
                    f[0][vecin] = 1;
                    dq.push_back(make_pair(0 , vecin));
                    if (doi[vecin] == -1){

                        dist[1][vecin] = 1 + dist[state][curr];
                        f[1][vecin] = 1;
                        dq.push_back(make_pair(1 , vecin));

                    }
                }
            }
            else if (prm[vecin] != curr && doi[vecin] == curr && !f[1][vecin]){
                if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){
                    dist[1][vecin] = 1 + dist[state][curr];
                    f[1][vecin] = 1;
                    dq.push_back(make_pair(1 , vecin));

                    if (doi[vecin] == -1){

                        dist[0][vecin] = 1 + dist[state][curr];
                        f[0][vecin] = 1;
                        dq.push_back(make_pair(0 , vecin));

                    }

                }
            }
        }


    }

    /// -----------------------------------------------------------------------------
    /// imi cer scuze alexandra daca citesti asta

    for (i = 1 ; i <= n ; i++){
        f[0][i] = f[1][i] = 0;
    }

    dq.push_back(make_pair(1 , p));
    f[1][p] = 1;
    while (!dq.empty()){

        state = dq.front().first;
        curr = dq.front().second;
        dq.pop_front();

        for (i = 0 ; i < v[curr].size() ; i++){
            vecin = v[curr][i];
            if (prm[vecin] == curr && !f[0][vecin]){
                if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){
                    far[0][vecin] = 1 + far[state][curr];
                    f[0][vecin] = 1;
                    dq.push_back(make_pair(0 , vecin));
                    if (doi[vecin] == -1){

                        far[1][vecin] = 1 + far[state][curr];
                        f[1][vecin] = 1;
                        dq.push_back(make_pair(1 , vecin));

                    }
                }
            }
            else if (prm[vecin] != curr && doi[vecin] == curr && !f[1][vecin]){
                if ((state == 0 && prm[curr] != vecin) || (state == 1 && prm[curr] == vecin)){
                    far[1][vecin] = 1 + far[state][curr];
                    f[1][vecin] = 1;
                    dq.push_back(make_pair(1 , vecin));

                    if (doi[vecin] == -1){

                        far[0][vecin] = 1 + far[state][curr];
                        f[0][vecin] = 1;
                        dq.push_back(make_pair(0 , vecin));

                    }

                }
            }
        }


    }


    /// mai fa un bfs aici ^^


    /// daca in nod ajungi pe muchia prm[nod] , o iei pe doi[nod], daca ea exista
    /// state = 0, esti libera sa o iei pe prm

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

        curr = i;
        state = 0;
        pc = 1;

        //printf ("\n\n%d\n\n" , i);

        while (!poz[state][curr]){

            //printf ("%d %d\n" , curr , state);

            poz[state][curr] = pc;
            pc++;

            if (state == 0 || doi[curr] == -1){
                vecin = prm[curr];

                if (prm[vecin] == curr && doi[vecin] != -1)
                    new_state = 1;
                else new_state = 0;
            }
            else {
                vecin = doi[curr];

                if (prm[vecin] == curr && doi[vecin] != -1)
                    new_state = 1;
                else new_state = 0;
            }


            /// din state, curr ----> new_state , vecin
            if (!poz[new_state][vecin])
                tt[new_state][vecin] = (state == 0 ? curr : -curr);
            else {
                old_state = state;
                old_curr = curr;
            }
            state = new_state;
            curr = vecin;
        }


        /// ai ajuns undeva unde ai mai fost

        if (!cod[state][curr]){ /// am descoperit acum un ciclu

            discovered = pc - poz[state][curr];

            cod[state][curr] = discovered;

            state = old_state;
            curr = old_curr;


            old_state = new_state;
            old_curr = vecin;


            while (curr != old_curr || state != old_state){

                cod[state][curr] = discovered;

                step_back(state , curr);
            }

            /// -------------------------------------------------------------------

            if (state == 0 && curr == i)
                continue;

            step_back(state , curr);

            dis = 1;


            while (curr != i || state != 0){

                len_cycle[state][curr] = discovered;
                cod[state][curr] = -dis;
                dis++;

                step_back(state , curr);
            }

            len_cycle[state][curr] = discovered;
            cod[state][curr] = -dis;


        }
        else { /// am dat de un drum deja descoperit

            if (pc == 1)
                continue;

            if (cod[state][curr] > 0){
                discovered = cod[state][curr];
                dis = 1;
            }
            else {
                discovered = len_cycle[state][curr];
                dis = -cod[state][curr] + 1;
            }

            state = old_state;
            curr = old_curr;

            while (curr != i || state != 0){

                len_cycle[state][curr] = discovered;
                cod[state][curr] = -dis;
                dis++;

                step_back(state , curr);

            }

            len_cycle[state][curr] = discovered;
            cod[state][curr] = -dis;

        }


    }


    /// cred ca am terminat precalcularea

    for (i = 0 ; i < q ; i++){
        len = g[i];
        sol = 0;
        for (j = 1 ; j <= n ; j++){

            //printf ("%d %d %d\n" , j , cod[0][j] , dist[0][j]);

            if (cod[0][j] > 0){ /// esti in ciclu
                if (dist[0][j] + 1 == (len + 1) % cod[0][j] || far[0][j] + 1 == (len + 1) % cod[0][j])
                    sol++;
            }
            else { /// verifica
                if (len <= -cod[0][j]){
                    if (dist[0][j] == len || far[0][j] == len)
                        sol++;
                }
                else {

                    len += cod[0][j];
                    len++;



                    if (dist[0][j] + 1 == len % (len_cycle[0][j]) || far[0][j] + 1 == len % (len_cycle[0][j]))
                        sol++;

                    len = g[i];

                }
            }

        }
        answer(sol);
    }


}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:70:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[curr].size() ; i++){
                      ~~^~~~~~~~~~~~~~~~
garden.cpp:122:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[curr].size() ; i++){
                      ~~^~~~~~~~~~~~~~~~
garden.cpp:273:30: warning: 'old_curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
             while (curr != i || state != 0){
                    ~~~~~~~~~~^~~~~~~~~~~~~
garden.cpp:273:30: warning: 'old_state' may be used uninitialized in this function [-Wmaybe-uninitialized]
garden.cpp:225:37: warning: 'new_state' may be used uninitialized in this function [-Wmaybe-uninitialized]
             while (curr != old_curr || state != old_state){
                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
garden.cpp:225:37: warning: 'vecin' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31