Submission #1066569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066569		fractlpaca	Tropical Garden (IOI11_garden)	C++17	49 / 100	5096 ms	12016 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> first (N, -1);
  v<int> second (N, -1);
  v<int> next (2*N, -1);
  
  // Build first and second choices
  for (int i=0; i<M; i++) {
    int a=R[i][0];
    int b=R[i][1];
    
    if (first[a]==-1) first[a]=b;
    else if (second[a]==-1) second[a]=b;
    
    if (first[b]==-1) first[b]=a;
    else if (second[b]==-1) second[b]=a;
  }
    
  for (int i=0; i<N; i++) {
    if (second[i]==-1) second[i]=first[i];
  }
  
  // Build next
  for (int i=0; i<N; i++) {
    if (first[first[i]]==i)  next[2*i]=first[i]*2+1;
    else next[2*i]=first[i]*2;
    
    if (first[second[i]]==i) next[2*i+1]=second[i]*2+1;
    else next[2*i+1]=second[i]*2;
  }

  
  //for (int i=0; i<N; i++) {
    //cerr<<i<<": ("<<next[2*i]/2<<","<<next[2*i]%2<<") ("<<next[2*i+1]/2<<","<<next[2*i+1]%2<<")"<<endl;
  //}
  
  int SUBTASK = 2;
  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
  
  
  // Build jump pointers
  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<2*N; j++) {
      jumps[i][j] = jumps[i-1][jumps[i-1][j]];
    }
  }
  
  //for (int j=0; j<2*N; j++) {
    //cerr<<j<<" ";
  //}cerr<<endl;
  //for (int i=0; i<=3; i++) {
    //for (int j=0; j<2*N; j++) {
      //cerr<<jumps[i][j]<<" ";
    //}cerr<<endl;
  //}
  
  if (SUBTASK==2) {
  
  for (int i=0; i<Q; i++) {
    int K=G[i];
    int count=0;
    
    for (int j=0; j<N; j++) {
      int end = jump_amount(jumps, 2*j, K);
      //cerr<<j<<" jumps "<<K<<" to ("<< end/2<<","<<end%2<<")"<<endl;
      if (end/2 == P) count++;
    }
    
    answer(count);
  }
  return;
  
  }
}

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