Submission #238177

#	Time	Username	Problem	Language	Result	Execution time	Memory
238177		Ruxandra985	Tropical Garden (IOI11_garden)	C++14	100 / 100	2824 ms	31904 KiB

garden

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


int f[2][DIMN] , taken[2][DIMN] , poz[2][DIMN] , taken_2[2][DIMN];
int dist[2][DIMN] , far[2][DIMN] , sol[2010];
vector < pair <int,int> > tt[2][DIMN];
pair <int , int> urm[2][DIMN];
int prm[DIMN] , doi[DIMN];
vector <int> v[DIMN];
deque <pair <int,int> > dq;

void calcul (int state , int curr , int n , int q , int g[]){
    int si , ci , dis , i , new_state , vecin , len1;

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

    si = state;
    ci = curr;

    dis = 0;

    while (!taken[state][curr]){
        taken[state][curr] = ++dis;
        new_state = urm[state][curr].first;
        vecin = urm[state][curr].second;
        state = new_state;
        curr = vecin;
    }
    if (state == si && curr == ci){ /// exista ciclu care il contine pe 0 , p
        len1 = dis; /// in muchii

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

            if (taken[0][i]){

                dist[0][i] = (dis - taken[0][i] + 1) % dis;
                dq.push_back(make_pair(0 , i));

            }

            if (taken[1][i]){

                dist[1][i] = (dis - taken[1][i] + 1) % dis;
                dq.push_back(make_pair(1 , i));

            }

        }

        while (!dq.empty()){

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

            if (state == 0){
                for (i = 0 ; i < q ; i++){
                    if (dist[state][curr] % len1 == g[i] % len1 && dist[state][curr] <= g[i]){
                        sol[i]++;
                        //if (si == 1)
                          //  printf ("%d %d\n" , state , curr);
                    }
                }
            }

            for (i = 0 ; i < tt[state][curr].size() ; i++){

                new_state = tt[state][curr][i].first;
                vecin = tt[state][curr][i].second;

                if ( taken[new_state][vecin] == 0 ){
                    dist[new_state][vecin] = 1 + dist[state][curr];
                    dq.push_back(make_pair(new_state , vecin));
                }

            }


        }



    }
    else { /// stare curr nu face parte din ciclu

        state = si;
        curr = ci;

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

        while (!dq.empty()){

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

            if (state == 0){
                for (i = 0 ; i < q ; i++){
                    if (dist[state][curr] - 1 == g[i])
                        sol[i]++;
                }
            }

            for (i = 0 ; i < tt[state][curr].size() ; i++){

                new_state = tt[state][curr][i].first;
                vecin = tt[state][curr][i].second;

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

            }


        }

    }



}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
    int i , curr , state , vecin , new_state , pc;

    p++;

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

    for (i = 1 ; i <= n ; i++){
        prm[i] = doi[i] = -1;
        poz[0][i] = poz[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];
    }

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


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

            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
            urm[state][curr] = make_pair(new_state , vecin);

            tt[new_state][vecin].push_back(make_pair(state , curr));

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

            state = new_state;
            curr = vecin;
        }

    }

    calcul (0 , p , n , q , g);

    calcul (1 , p , n , q , g);



    for (i = 0 ; i < q ; i++)
        answer(sol[i]);


}

Compilation message (stderr)

garden.cpp: In function 'void calcul(int, int, int, int, int*)':
garden.cpp:72:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i = 0 ; i < tt[state][curr].size() ; i++){
                          ~~^~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:111:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i = 0 ; i < tt[state][curr].size() ; i++){
                          ~~^~~~~~~~~~~~~~~~~~~~~~~~

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