제출 #347158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347158		daniel920712	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	3349 ms	78264 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include "gardenlib.h"
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
int con[150005]={0};
bool have[5][150005];
int st,aaa,bbb;
int con1[5][150005];
int con2[5][150005];

int cir1[5][150005];
int cir2[5][150005];
int in[5][150005];
bool ok=0;
map < pair < int , int > , int  > all;
vector < pair < int , int > > Next[1500005];
void F(int x,int y,int deg,int a,int b)
{
    //printf("aa %d %d %d %d %d %d\n",x,y,a,b,con1[x][y],con2[x][y]);
    int t,aa,bb;
    if(have[x][y])
    {
        if(all.find(make_pair(x,y))!=all.end())
        {
            ok=1;
            t=all[make_pair(x,y)];
            aaa=x;
            bbb=y;
            //printf("%d\n",t);
            if(a!=-1&&a>=t)
            {
                cir1[x][y]=deg-t;
                con1[x][y]=cir1[x][y]-(deg-all[make_pair(0,st)]);
                con1[x][y]%=cir1[x][y];
            }

            if(b!=-1&&b>=t)
            {
                cir2[x][y]=deg-t;
                con2[x][y]=cir2[x][y]-(deg-all[make_pair(1,st)]);
                con2[x][y]%=cir2[x][y];
            }
        }
        //printf("%d %d %d %d %d %d\n",x,y,con1[x][y],cir1[x][y],con2[x][y],cir2[x][y]);
        return;
    }
    have[x][y]=1;
    all[make_pair(x,y)]=deg;

    if(x==0&&y==st)
    {
        a=deg;
        if(!ok)
        {
            cir1[x][y]=-1;
            con1[x][y]=0;
        }
    }
    if(x==1&&y==st)
    {
        b=deg;
        if(!ok)
        {
            cir2[x][y]=-1;
            con2[x][y]=0;
        }
    }
    if(y==Next[Next[y][x].second][0].second&&con[Next[y][x].second]>1)
    {
        aa=1;
        bb=Next[y][x].second;
    }
    else
    {
        aa=0;
        bb=Next[y][x].second;
    }
    F(aa,bb,deg+1,a,b);
    //printf("xx %d %d %d %d %d %d %d\n",x,y,aa,bb,con1[aa][bb],con2[aa][bb],con1[x][y]);
    if(con1[aa][bb]!=-1)
    {
        con1[x][y]=con1[aa][bb]+1;
        cir1[x][y]=cir1[aa][bb];
        if(ok&&cir1[x][y]!=-1) con1[x][y]%=cir1[x][y];
    }
    if(con2[aa][bb]!=-1)
    {
        con2[x][y]=con2[aa][bb]+1;
        cir2[x][y]=cir2[aa][bb];
        if(ok&&cir2[x][y]!=-1) con2[x][y]%=cir2[x][y];
    }
    if(x==aaa&&y==bbb) ok=0;
    //printf("yy %d %d %d %d %d %d\n",x,y,con1[x][y],cir1[x][y],con2[x][y],cir2[x][y]);
}

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;
    st=P;
    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][1].second]>1&&i==Next[Next[i][1].second][0].second) in[1][Next[i][1].second]++;
        else if(con[i]>1) in[0][Next[i][1].second]++;

        con1[0][i]=-1;
        con1[1][i]=-1;
        con2[1][i]=-1;
        con2[0][i]=-1;

        cir1[0][i]=-1;
        cir1[1][i]=-1;

        cir2[1][i]=-1;
        cir2[0][i]=-1;
    }
    for(i=0;i<N;i++)
    {


        all.clear();
        if(in[0][i]==0) F(0,i,0,-1,-1);

        all.clear();
        if(in[1][i]==0&&con[i]>1) F(1,i,0,-1,-1);

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

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

    }
    for(i=0;i<Q;i++)
    {
        ans=0;
        for(j=0;j<N;j++)
        {
            if(G[i]==con1[0][j]||G[i]==con2[0][j]) ans++;
            else if(cir1[0][j]!=-1&&con1[0][j]!=-1&&G[i]>=con1[0][j]&&(G[i]-con1[0][j])%cir1[0][j]==0) ans++;
            else if(cir2[0][j]!=-1&&con2[0][j]!=-1&&G[i]>=con2[0][j]&&(G[i]-con2[0][j])%cir2[0][j]==0) ans++;
        }
        answer((int) ans);
    }


}

컴파일 시 표준 에러 (stderr) 메시지

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

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