Submission #1183228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183228		hamzabc	Tropical Garden (IOI11_garden)	C++20	69 / 100	5090 ms	89672 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;


struct node{
  int primer = -1;
  int seconder = -1;
  vector<pair<int, bool>> pbinlift;
  vector<pair<int, bool>> sbinlift;
};


vector<node> graph;


void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  graph.resize(N);
  for (int i = 0; i < N; i++){
    graph[i].pbinlift.resize(32);
    graph[i].sbinlift.resize(32);
  }
  for (int i = 0; i < M; i++){
    if (graph[R[i][0]].primer == -1){
      graph[R[i][0]].primer = R[i][1];
      graph[R[i][0]].pbinlift[0].first = R[i][1];
      graph[R[i][0]].pbinlift[0].second = (graph[R[i][1]].primer == -1);
    }else if (graph[R[i][0]].seconder == -1){
      graph[R[i][0]].seconder = R[i][1];
      graph[R[i][0]].sbinlift[0].first = R[i][1];
      graph[R[i][0]].sbinlift[0].second = (graph[R[i][1]].primer == -1);
    }
    if (graph[R[i][1]].primer == -1){
      graph[R[i][1]].primer = R[i][0];
      graph[R[i][1]].pbinlift[0].first = R[i][0];
      graph[R[i][1]].pbinlift[0].second = (graph[R[i][0]].primer == R[i][1]);
    }else if (graph[R[i][1]].seconder == -1){
      graph[R[i][1]].seconder = R[i][0];
      graph[R[i][1]].sbinlift[0].first = R[i][0];
      graph[R[i][1]].sbinlift[0].second = (graph[R[i][0]].primer == R[i][1]);
    }
  }
  for (int i = 0; i < N; i++){
    if (graph[i].pbinlift[0].second && graph[graph[i].pbinlift[0].first].seconder == -1)
      graph[i].pbinlift[0].second = false;
    if (graph[i].sbinlift[0].second && graph[graph[i].sbinlift[0].first].seconder == -1)
      graph[i].sbinlift[0].second = false;
  }
  for (int i = 1; i < 32; i++){
    for (int o = 0; o < N; o++){
      if (graph[o].pbinlift[i - 1].second){
        graph[o].pbinlift[i].first = graph[graph[o].pbinlift[i - 1].first].sbinlift[i - 1].first;
        graph[o].pbinlift[i].second = graph[graph[o].pbinlift[i - 1].first].sbinlift[i - 1].second;
      }else{
        graph[o].pbinlift[i].first = graph[graph[o].pbinlift[i - 1].first].pbinlift[i - 1].first;
        graph[o].pbinlift[i].second = graph[graph[o].pbinlift[i - 1].first].pbinlift[i - 1].second;
      }
      if (graph[o].sbinlift[i - 1].second){
        graph[o].sbinlift[i].first = graph[graph[o].sbinlift[i - 1].first].sbinlift[i - 1].first;
        graph[o].sbinlift[i].second = graph[graph[o].sbinlift[i - 1].first].sbinlift[i - 1].second;
      }else{
        graph[o].sbinlift[i].first = graph[graph[o].sbinlift[i - 1].first].pbinlift[i - 1].first;
        graph[o].sbinlift[i].second = graph[graph[o].sbinlift[i - 1].first].pbinlift[i - 1].second;
      }
    }
  }
  for (int i = 0; i < Q; i++){
    long long int say = 0;
    for (int o = 0; o < N; o++){
      int p = o;
      bool k = false;
      int m = G[i];
      for (int j = 31; j >= 0; j--){
        if (m >= (1LL << j)){
          m -= (1LL << j);
          if (k){
            k = graph[p].sbinlift[j].second;
            p = graph[p].sbinlift[j].first;
          }else{
            k = graph[p].pbinlift[j].second;
            p = graph[p].pbinlift[j].first;
          }
        }
      }
      if (p == P)
        say++;
    }
    answer(say);
  }
}

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