Submission #347148

#	Time	Username	Problem	Language	Result	Execution time	Memory
347148		daniel920712	Tropical Garden (IOI11_garden)	C++14	69 / 100	5065 ms	72172 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include "gardenlib.h"
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
long long con[150005]={0};
vector < pair < long long , long long > > Next[150005];
vector < pair < long long , long long > > tt[5][150005];
vector < pair < long long , long long > > tt2[5][150005];
pair < long long , long long > Father[5][150005];
long long how[5][150005];
long long circle[5][150005];
long long Deg[5][150005];
pair < long long , long long > st[5][150005];
bool is[5][150005];
long long in[5][150005]={0};
bool have[5][150005]={0};
long long where[5][150005];
long long ok=0;
long long stx,sty;
vector < pair < long long , long long > > all;
void F(long long x,long long 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(long long x,long long y)
{
    long long ok=0,deg=0;
    st[x][y]=make_pair(stx,sty);

    for(auto i:all)
    {
        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[stx][sty].push_back(i);
            is[i.first][i.second]=1;
            how[i.first][i.second]=deg++;
        }
        else
        {
            tt[x][y].push_back(i);
            Father[i.first][i.second]=make_pair(x,y);
            how[i.first][i.second]=deg++;
        }
    }

    if(ok) Deg[stx][sty]=deg;
    else
    {
        tt[x][y].push_back(make_pair(stx,sty));
        Deg[x][y]=deg;
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    long long i=0,j,k,where,ans=0,real;
    pair < long long , long long > 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]++;
    }

    for(i=0;i<N;i++)
    {
        stx=-1;
        sty=-1;
        all.clear();
        if(in[0][i]==0)
        {
            F(0,i);
            FF(0,i);
        }
        stx=-1;
        sty=-1;
        all.clear();
        if(in[1][i]==0&&con[i]>1)
        {
            F(1,i);
            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++)
        {
            now=make_pair(0,j);
            real=G[i];
            where=j;
            while(!is[now.first][now.second])
            {
                real+=how[now.first][now.second];
                now=Father[now.first][now.second];
                if(real<=Deg[now.first][now.second])
                {
                    where=tt[now.first][now.second][real].second;
                    real=0;
                    break;
                }
                else
                {
                    real-=Deg[now.first][now.second];
                    now=st[now.first][now.second];
                }
            }
            if(real)
            {
                real+=how[now.first][now.second];
                now=Father[now.first][now.second];
                where=tt2[now.first][now.second][(real)%Deg[now.first][now.second]].second;

            }
            //printf("%d %d\n",j,where);
            if(where==P) ans++;
        }
        answer((int) 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:75:21: warning: unused variable 'k' [-Wunused-variable]
   75 |     long long i=0,j,k,where,ans=0,real;
      |                     ^

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