Submission #247677

#	Time	Username	Problem	Language	Result	Execution time	Memory
247677		davi_bart	Tropical Garden (IOI11_garden)	C++14	69 / 100	5068 ms	47864 KiB

garden

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
typedef long long ll;
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v[200010];
int p[30][300010];
int n;
int sol(int P,int k,int pos){
  for(int i=0;i<30;i++){
    if(k&(1<<i))pos=p[i][pos];
  }
  if(pos==P || pos==n+P)return 1;
  return 0;
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
  n=N;
  for(int i=0;i<M;i++){
    if(v[R[i][0]].size()<2)v[R[i][0]].push_back(R[i][1]);
    if(v[R[i][1]].size()<2)v[R[i][1]].push_back(R[i][0]);
  }
  for(int i=0;i<N;i++){
    p[0][i]=v[i][0];
    if(v[v[i][0]][0]==i)p[0][i]+=N;
  }
  for(int i=0;i<N;i++){
    p[0][i+N]=v[i].back();
    if(v[v[i].back()][0]==i)p[0][i+N]+=N;
  }
  for(int i=1;i<30;i++){
    for(int j=0;j<2*N;j++){
      p[i][j]=p[i-1][p[i-1][j]];
    }
  }
  for(int i=0;i<Q;i++){
    int tot=0;
    for(int j=0;j<N;j++)tot+=sol(P,G[i],j);
    answer(tot);
  }
}

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