Submission #347129

#	Time	Username	Problem	Language	Result	Execution time	Memory
347129		daniel920712	Tropical Garden (IOI11_garden)	C++14	0 / 100	79 ms	79468 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include "gardenlib.h"
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int con[150005]={0};
vector < pair < int , int > > Next[150005];
vector < pair < int , int > > tt[5][150005];
vector < pair < int , int > > tt2[5][150005];
pair < int , int > Father[5][150005];
int how[5][150005];
int circle[5][150005];
int Deg[5][150005];
pair < int , int > st[5][150005];
bool is[5][150005];
int in[5][150005]={0};
bool have[5][150005]={0};
int where[5][150005];
int ok=0;
int stx,sty;
vector < pair < int , int > > all;
void F(int x,int y)
{
    if(have[x][y])
    {
        stx=x;
        sty=y;
        return;
    }
    have[x][y]=1;
    all.push_back(make_pair(x,y));
    if(y==Next[Next[y][x].second][0].second&&con[Next[y][x].second]>1) F(1,Next[y][x].second);
    else F(0,Next[y][x].second);
}
void FF(int x,int y)
{
    int ok=0,deg=0;
    st[x][y]=make_pair(stx,sty);
    for(auto i:all)
    {
        //printf("%d %d\n",i.first,i.second);
        if(i==make_pair(stx,sty))
        {
            tt[x][y].push_back(i);
            Deg[x][y]=deg;
            ok=1;
            deg=0;
        }
        if(ok)
        {
            Father[i.first][i.second]=make_pair(stx,sty);
            tt2[x][y].push_back(i);
            is[i.first][i.second]=1;
            how[i.first][i.second]=deg++;
        }
        else
        {
            tt[x][y].push_back(i);
            is[i.first][i.second]=1;
            Father[i.first][i.second]=make_pair(x,y);
            how[i.first][i.second]=deg++;
        }
    }

    if(ok) circle[stx][sty]=deg;

}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i=0,j,k,where,ans=0,real;
    pair < int , int > now;
    for(i=0;i<M;i++)
    {
        Next[R[i][0]].push_back(make_pair(i,R[i][1]));
        Next[R[i][1]].push_back(make_pair(i,R[i][0]));
        con[R[i][0]]++;
        con[R[i][1]]++;
    }
    for(i=0;i<N;i++) sort(Next[i].begin(),Next[i].end());
    for(i=0;i<N;i++)
    {
        if(i==Next[Next[i][0].second][0].second&&con[Next[i][0].second]>1) in[1][Next[i][0].second]++;
        else in[0][Next[i][0].second]++;

        if(con[i]>1&&con[Next[i][0].second]>1&&i==Next[Next[i][0].second][1].second) in[1][Next[i][1].second]++;
        else if(con[i]>1) in[0][Next[i][1].second]++;
    }

    for(i=0;i<N;i++)
    {
        stx=-1;
        sty=-1;
        all.clear();
        if(in[0][i]==0)
        {
            F(0,i);
            //printf("aa\n");
            FF(0,i);
        }

        stx=-1;
        sty=-1;
        all.clear();
        if(in[1][i]==0&&con[i]>1)
        {
            F(1,i);
            //printf("aa\n");
            FF(1,i);
        }
    }

    for(i=0;i<N;i++)
    {
        stx=-1;
        sty=-1;
        all.clear();
        if(have[0][i]==0)
        {
            F(0,i);
            FF(0,i);
        }

        stx=-1;
        sty=-1;
        all.clear();
        if(have[1][i]==0&&con[i]>1)
        {
            F(1,i);
            FF(1,i);
        }
    }

    for(i=0;i<Q;i++)
    {
        ans=0;
        for(j=0;j<N;j++)
        {
            if(is[0][j])
            {
                now=Father[0][j];
                where=tt2[now.first][now.second][(how[0][j]+G[i])%Deg[now.first][now.second]].second;
                if(where==P) ans++;
            }
            else
            {
                real=G[i]+Deg[Father[0][j].first][Father[0][j].second];
                now=Father[0][j];
                if(real<Deg[now.first][now.second])
                {
                    where=tt[now.first][now.second][real].second;
                }
                else
                {
                    real-=Deg[now.first][now.second];
                    now=st[now.first][now.second];

                    where=tt2[now.first][now.second][(real)%Deg[now.first][now.second]].second;

                }
                if(where==P) ans++;
            }
        }
        answer(ans);
    }


}
/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5

1
3

2
*/

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:72:15: warning: unused variable 'k' [-Wunused-variable]
   72 |     int i=0,j,k,where,ans=0,real;
      |               ^

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