Submission #895125

#	Time	Username	Problem	Language	Result	Execution time	Memory
895125		anton	Tropical Garden (IOI11_garden)	C++17	69 / 100	5038 ms	97692 KiB

garden

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

using namespace std;
#define pii pair<int, int>


const int MAX_N = 2*1e5;
pii bl[2*MAX_N][30];

int max_p[MAX_N];

int to_id(pii pos){
  return pos.first*MAX_N+ pos.second;
}
vector<vector<pii>> adj;

int get_step(int id, int d){
  int cur = id;
  for(int i = 0; i<30; i++){
    if((d& (1<<i)) != 0){
      if(bl[cur][i].first == max_p[bl[cur][i].second]){
        cur = bl[cur][i].second + MAX_N;
      }
      else{
        cur = bl[cur][i].second;
      }
    }
  }
  return cur;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  adj.resize(N);
  for(int i = 0; i <M; i++){
    adj[R[i][0]].push_back(pii(i, R[i][1]));
    adj[R[i][1]].push_back(pii(i, R[i][0]));
  }
  for(int i = 0; i<N; i++){
    bl[i][0] = adj[i][0];
    max_p[i] = adj[i][0].first;
    if(adj[i].size()>1){
      bl[i+MAX_N][0] = adj[i][1];
    }
    else{
      bl[i+MAX_N][0] = adj[i][0];
    }
  }


  for(int i = 1; i<30; i++){
    for(int j = 0; j<N; j++){
      if(bl[j][i-1].first == max_p[bl[j][i-1].second]){
        bl[j][i] = bl[bl[j][i-1].second + MAX_N][i-1];
      }
      else{
        bl[j][i] = bl[bl[j][i-1].second][i-1];
      }
    }

    for(int j = 0; j<N+MAX_N; j++){
      if(bl[j][i-1].first == max_p[bl[j][i-1].second]){
        bl[j][i] = bl[bl[j][i-1].second + MAX_N][i-1];
      }
      else{
        bl[j][i] = bl[bl[j][i-1].second][i-1];
      }
    }
  }

  for(int i = 0; i<Q; i++){
    int res= 0;
    for(int j = 0; j<N; j++){
      if(get_step(j, G[i])%MAX_N == P){
        res++;
      }
    }
    answer(res);
  }
}

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