Submission #18630

#	Time	Username	Problem	Language	Result	Execution time	Memory
18630		ggoh	Tropical Garden (IOI11_garden)	C++98	100 / 100	2725 ms	11892 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
int a,b,c,t,h,p,q,check,p1,q1,y,z,sz1,sz2,v[150003][2],ch2[150003][2],ch1[150003][2],x[150003][2],D1[150003][2],D2[150003][2],cycle1[150003][2],cycle2[150003][2];
void count_routes(int N,int M,int P,int R[][2],int Q,int G[])
{
    a=N;b=M;
    c=P+1;
    for(int i=0;i<b;i++)
    {
        if(x[R[i][0]+1][0]==0)x[R[i][0]+1][0]=R[i][1]+1;
        else if(x[R[i][0]+1][1]==0)x[R[i][0]+1][1]=R[i][1]+1;
        if(x[R[i][1]+1][0]==0)x[R[i][1]+1][0]=R[i][0]+1;
        else if(x[R[i][1]+1][1]==0)x[R[i][1]+1][1]=R[i][0]+1;
    }
    for(int i=1;i<=a;i++)
    {
        if(x[i][1]==0)x[i][1]=x[i][0];
    }
    p=c;q=0;t=0;
    D1[p][q]=0;
    ch1[p][q]=1;

    v[p][q]=1;
    p1=-1;q1=-1;
    while(1)
    {
        if(q==0)p1=x[p][0];
        else p1=x[p][1];
        if(p==x[p1][0])q1=1;
        else q1=0;
        if(p1==c&&q1==0)break;
        else
        {
            if(v[p1][q1]==1)break;
            v[p1][q1]=1;
            p=p1;q=q1;
            t++;
        }
    }
    if(p1==c&&q1==0)
    {
        p=c;q=0;
        cycle1[p][q]=t+1;
        while(1)
        {
            if(q==0)p1=x[p][0];
            else p1=x[p][1];
            if(p==x[p1][0])q1=1;
            else q1=0;
            if(p1==c&&q1==0)break;
            p=p1;q=q1;
            ch1[p][q]=1;
            D1[p][q]=t;t--;
            cycle1[p][q]=cycle1[c][0];
        }
    }
    memset(v,0,sizeof(v));

    p=c;q=1;t=0;
    D2[p][q]=0;
    ch2[p][q]=1;

    v[p][q]=1;
    p1=-1;q1=-1;
    while(1)
    {
        if(q==0)p1=x[p][0];
        else p1=x[p][1];
        if(p==x[p1][0])q1=1;
        else q1=0;
        if(p1==c&&q1==1)break;
        else
        {
            if(v[p1][q1]==1)break;
            v[p1][q1]=1;
            p=p1;q=q1;
            t++;
        }
    }
    if(p1==c&&q1==1)
    {
        p=c;q=1;
        cycle2[p][q]=t+1;
        while(1)
        {
            if(q==0)p1=x[p][0];
            else p1=x[p][1];
            if(p==x[p1][0])q1=1;
            else q1=0;
            if(p1==c&&q1==1)break;
            p=p1;q=q1;
            ch2[p][q]=1;
            D2[p][q]=t;
            cycle2[p][q]=cycle2[c][1];
            t--;
        }
    }

    memset(v,0,sizeof(v));
    for(int i=1;i<=a;i++)
    {
        for(int j=0;j<2;j++)
        {
            if(ch1[i][j])continue;
            p=i;q=j;t=0;
            v[i][j]=1;
            while(1)
            {
                if(q==0)p1=x[p][0];
                else p1=x[p][1];
                if(p==x[p1][0])q1=1;
                else q1=0;
                t++;
                if(ch1[p1][q1])break;
                else if(v[p1][q1])break;
                p=p1;q=q1;
                v[p][q]=1;
            }
            if(ch1[p1][q1])
            {
                y=p1;z=q1;
                p=i;q=j;
                ch1[p][q]=1;
                D1[p][q]=D1[y][z]+t;
                cycle1[p][q]=cycle1[y][z];
                while(1)
                {
                    if(q==0)p1=x[p][0];
                    else p1=x[p][1];
                    if(p==x[p1][0])q1=1;
                    else q1=0;
                    t--;
                    if(p1==y&&q1==z)break;
                    p=p1;q=q1;
                    ch1[p][q]=1;
                    D1[p][q]=D1[y][z]+t;
                    cycle1[p][q]=cycle1[y][z];
                }
            }
        }
    }
    memset(v,0,sizeof(v));
    for(int i=1;i<=a;i++)
    {
        for(int j=0;j<2;j++)
        {
            if(ch2[i][j])continue;
            p=i;q=j;t=0;
            v[i][j]=1;
            while(1)
            {
                if(q==0)p1=x[p][0];
                else p1=x[p][1];
                if(p==x[p1][0])q1=1;
                else q1=0;
                t++;
                if(ch2[p1][q1])break;
                else if(v[p1][q1])break;
                p=p1;q=q1;
                v[p][q]=1;
            }
            if(ch2[p1][q1])
            {
                y=p1;z=q1;
                p=i;q=j;
                ch2[p][q]=1;
                D2[p][q]=D2[y][z]+t;
                cycle2[p][q]=cycle2[y][z];
                while(1)
                {
                    if(q==0)p1=x[p][0];
                    else p1=x[p][1];
                    if(p==x[p1][0])q1=1;
                    else q1=0;
                    t--;
                    if(p1==y&&q1==z)break;
                    p=p1;q=q1;
                    ch2[p][q]=1;
                    D2[p][q]=D2[y][z]+t;
                    cycle2[p][q]=cycle2[y][z];
                }
            }
        }
    }
    int ans;
    for(int i=0;i<Q;i++)
    {
        ans=0;
        for(int j=1;j<=a;j++)
        {
            if(ch1[j][0]&&(D1[j][0]==G[i]||(cycle1[j][0]&&G[i]>D1[j][0]&&(G[i]-D1[j][0])%cycle1[j][0]==0)))
            {
                ans++;
            }
            else if(ch2[j][0]&&(D2[j][0]==G[i]||(cycle2[j][0]&&G[i]>D2[j][0]&&(G[i]-D2[j][0])%cycle2[j][0]==0)))
            {
                ans++;
            }
        }
        answer(ans);
    }
}

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