Submission #1065776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065776		fractlpaca	Tropical Garden (IOI11_garden)	C++17	0 / 100	1 ms	344 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
#define v vector
#define pii pair<int,int>
#define ll long long
#define pli pair<long long, int>
#define fi first
#define se second

using namespace std;


int LIMIT = 29;
int jump_amount(v<v<int>> jumps, int a, int amount) {
  for (int j=LIMIT; j>=0; j--) {
    if (1<<j <= amount) {
      amount -= 1<<j;
      a = jumps[j][a];
    }
  }
  return a;
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  v<int> next (2*N, -1);
  
  for (int i=0; i<M; i++) {
    int a=R[i][0];
    int b=R[i][1];
    
    if (next[2*a]==-1 && next[2*b]==-1) {
      next[2*a]=2*b+1;
      next[2*b]=2*a+1;
      continue;
    }
    
    if (next[2*a]==-1) next[2*a]=2*b;
    else if (next[2*a+1]==-1) next[2*a+1]=2*b;
    
    if (next[2*b]==-1) next[2*b]=2*a;
    else if (next[2*b+1]==-1) next[2*b+1]=2*a;
  }
  
  for (int i=0; i<N; i++) {
    if (next[2*i+1]==-1) next[i*2+1]=next[i*2];
  }
  
  int SUBTASK = 1;
  if (SUBTASK==1) {
  
  assert(Q==1);
  
  int K=G[0];
  int count = 0;
  for (int i=0; i<N; i++) {
    int cur=2*i;
    for (int j=0; j<K; j++) {
      cur = next[cur];
    }
    if (cur/2 == P) count++;
  }
  answer(count);
  return;
  
  }
  
  // Both subtasks 2&3
  
  
  v<v<int>> jumps (LIMIT+1, v<int> (2*N, 0));
  jumps[0] = next;
  for (int i=1; i<=LIMIT; i++) {
    for (int j=0; j<N; j++) {
      jumps[i][j] = jumps[i-1][jumps[i-1][j]];
    }
  }
  
  if (SUBTASK==2) {
  
  for (int i=0; i<Q; i++) {
    int K=G[i];
    int count=0;
    
    for (int j=0; j<N; j++) {
      if (jump_amount(jumps, 2*j, K)/2 == P) count++;
    }
    
    answer(count);
  }
  return;
  
  }
}

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