Submission #1113900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113900		yarengkm	Tropical Garden (IOI11_garden)	C++17	69 / 100	5075 ms	105300 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define pb push_back
#define pi pair<int,int>
#define fi first
#define se second 
using namespace std;
const int maxn=2*1e5;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  vector<int>adj[maxn];
  vector<pair<int,int>>c1[maxn];
  vector<pair<int,int>>c2[maxn];
  for(int i=0;i<M;i++){
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }
  for(int i=0;i<N;i++){
    pi p={0,0};
    p.fi=adj[i][0];
    if(adj[p.fi][0]==i)p.se=1;
    c1[i].pb(p);
    if(adj[i].size()>1){
      p.fi=adj[i][1];
      if(adj[p.fi][0]==i)p.se=1;
      else p.se=0;
    }
    c2[i].pb(p);
  }
  for(int i=1;i<=ceil(log2(1e9));i++){
    for(int j=0;j<N;j++){
      pair<int,int>p=c1[j][i-1];
      if(p.se==0)p=c1[p.fi][i-1];
      else p=c2[p.fi][i-1];
      c1[j].pb(p);
      p=c2[j][i-1];
      if(p.se==0)p=c1[p.fi][i-1];
      else p=c2[p.fi][i-1];
      c2[j].pb(p);
    }
  }
  for(int i=0; i<Q; i++){
    int k=G[i];
    int ans=0;
    for(int m=0;m<N;m++){
      pi p={m,0};
      int cur=0;
      k=G[i];
      for(int j=ceil(log2(1e9));j>=0;j--){
        if(k>=(1<<j)){
          if(cur==0)p=c1[p.fi][j];
          else p=c2[p.fi][j];
          cur=p.se;
          k-=(1<<j);
        }
      }
      if(p.fi==P)ans++;
    }
    answer(ans);
  }
}
  

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