Submission #347798

#	Time	Username	Problem	Language	Result	Execution time	Memory
347798		juggernaut	Tropical Garden (IOI11_garden)	C++14	69 / 100	196 ms	50412 KiB

garden

#include"garden.h"
#include"gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef EVAL
#else
#include"grader.cpp"
#endif
#define pb push_back
int go[300005][30];
vector<int>g[300005];
void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
    memset(go,-1,sizeof(go));
    for(int i=0;i<M;i++){
        int x=R[i][0],y=R[i][1];
        if(g[x].size()<2)g[x].pb(y);
        if(g[y].size()<2)g[y].pb(x);
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<g[i].size();j++){
            int to=g[i][j];
            if(g[to][0]==i&&g[to].size()>1)go[i+j*N][0]=to+N;
            else go[i+j*N][0]=to;
        }
    for(int j=1;j<30;j++)
        for(int i=0;i<(N<<1);i++)
            if(go[i][j-1]!=-1)go[i][j]=go[go[i][j-1]][j-1];
    int cnt=0;
    for(int i=0;i<N;i++){
        int k=G[0],node=i;
        for(int j=29;j>=0;j--)if(k>=(1<<j))node=go[node][j],k-=(1<<j);
        cnt+=(node==P||node==P+N);
    }
    answer(cnt);
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int j=0;j<g[i].size();j++){
      |                     ~^~~~~~~~~~~~

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