Submission #7511

#	Time	Username	Problem	Language	Result	Execution time	Memory
7511		baneling100	Tropical Garden (IOI11_garden)	C++98	100 / 100	4106 ms	9772 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <vector>
#define INF 0x7fffffff

using namespace std;

int First[150001], Second[150001], A[300001], D[300001][2], Check[300001], K, Cycle1, Cycle2;

void DFS(int Now)
{
    if(!Check[A[Now]])
    {
        Check[A[Now]]=1;
        DFS(A[Now]);
    }
    if(D[A[Now]][K]!=INF)
        D[Now][K]=D[A[Now]][K]+1;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i, j, Cnt;

    for(i=0 ; i<N ; i++)
        First[i]=Second[i]=-1;
    for(i=0 ; i<M ; i++)
    {
        if(First[R[i][0]]==-1)
            First[R[i][0]]=R[i][1];
        else if(Second[R[i][0]]==-1)
            Second[R[i][0]]=R[i][1];
        if(First[R[i][1]]==-1)
            First[R[i][1]]=R[i][0];
        else if(Second[R[i][1]]==-1)
            Second[R[i][1]]=R[i][0];
    }
    for(i=0 ; i<N ; i++)
    {
        if(Second[i]==-1)
        {
            if(First[First[i]]==i)
                A[2*i]=2*First[i];
            else
                A[2*i]=2*First[i]+1;
            A[2*i+1]=-1;
        }
        else
        {
            if(First[Second[i]]==i)
                A[2*i]=2*Second[i];
            else
                A[2*i]=2*Second[i]+1;
            if(First[First[i]]==i)
                A[2*i+1]=2*First[i];
            else
                A[2*i+1]=2*First[i]+1;
        }
    }
    K=0;
    for(i=0 ; i<2*N ; i++)
    {
        Check[i]=0;
        D[i][0]=INF;
    }
    Check[2*P]=1;
    D[2*P][0]=0;
    for(i=0 ; i<2*N ; i++)
        if(A[i]!=-1 && !Check[i])
        {
            Check[i]=1;
            DFS(i);
        }
    if(A[2*P+1]!=-1)
    {
        K=1;
        for(i=0 ; i<2*N ; i++)
        {
            Check[i]=0;
            D[i][1]=INF;
        }
        Check[2*P+1]=1;
        D[2*P+1][1]=0;
        for(i=0 ; i<2*N ; i++)
            if(A[i]!=-1 && !Check[i])
            {
                Check[i]=1;
                DFS(i);
            }
    }
    if(D[A[2*P]][0]!=INF)
        Cycle1=D[A[2*P]][0]+1;
    if(Second[P]!=-1 && D[A[2*P+1]][1]!=INF)
        Cycle2=D[A[2*P+1]][1]+1;
    for(i=0 ; i<Q ; i++)
    {
        Cnt=0;
        for(j=0 ; j<2*N ; j++)
            if((j%2==0 && Second[j/2]==-1) || (j%2==1 && Second[j/2]!=-1))
            {
                if(Cycle1)
                {
                    if(G[i]>=D[j][0] && (G[i]-D[j][0])%Cycle1==0)
                    {
                        Cnt++;
                        continue;
                    }
                }
                else
                {
                    if(G[i]==D[j][0])
                    {
                        Cnt++;
                        continue;
                    }
                }
                if(Second[P]!=-1)
                {
                    if(Cycle2)
                    {
                        if(G[i]>=D[j][1] && (G[i]-D[j][1])%Cycle2==0)
                        {
                            Cnt++;
                            continue;
                        }
                    }
                    else
                        if(G[i]==D[j][1])
                        {
                            Cnt++;
                            continue;
                        }
                }
            }
        answer(Cnt);
    }
}

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