Submission #345135

#	Time	Username	Problem	Language	Result	Execution time	Memory
345135		daniel920712	Tropical Garden (IOI11_garden)	C++14	0 / 100	4 ms	3564 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include "gardenlib.h"
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int con[100005];
vector < pair < int , int > > Next[100005];
pair < int , int > tra[2][31][100005];
int Father[100005];
bool F(int fa,int here,int how,int where,int deg)
{
    if(deg==how) return where==here;
    if(con[here]==1||fa!=Next[here][0].second) return F(here,Next[here][0].second,how,where,deg+1);
    else return F(here,Next[here][1].second,how,where,deg+1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i,now=0,j,k;
    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());
        if(con[i]==1) Father[i]=-1;
        else Father[i]=Next[i][0].first;
        //printf("%d\n",Father[i]);
    }
    for(i=0;i<N;i++)
    {
        tra[0][0][i]=make_pair(i,Next[i][0].second);
        if(Father[i]!=-1) tra[1][0][i]=make_pair(i,Next[i][1].second);
    }
    for(i=1;i<=30;i++)
    {
        for(j=0;j<N;j++)
        {
            if(tra[0][i-1][j].first==Father[tra[0][i-1][j].second]) tra[0][i][j]=tra[1][i-1][tra[0][i-1][j].second];
            else tra[0][i][j]=tra[0][i-1][tra[0][i-1][j].second];

            if(tra[1][i-1][j].first==Father[tra[1][i-1][j].second]) tra[1][i][j]=tra[1][i-1][tra[1][i-1][j].second];
            else tra[1][i][j]=tra[0][i-1][tra[1][i-1][j].second];
        }
    }

    for(i=0;i<Q;i++)
    {
        //printf("aa\n");
        now=0;
        for(j=0;j<N;j++)
        {
            pair < int , int > tt=make_pair(-2,j);
            for(k=0;k<=30;k++)
            {
                if(G[i]&(1<<k))
                {
                    //printf("%d %d ",tt.first,tt.second);
                    if(Father[tt.second]!=-1&&tt.first==Father[tt.second]) tt=tra[1][k][tt.second];
                    else tt=tra[0][k][tt.second];
                    //printf("%d %d\n",tt.first,tt.second);
                }
            }
            //printf("%d %d\n",j,tt.second);
            if(tt.second==P) now++;

        }
        answer(now);
    }

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

1
3

2
*/

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