Submission #1036931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036931		aaaaaarroz	Tropical Garden (IOI11_garden)	C++17	69 / 100	5033 ms	84560 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150000;
const int MAXLOG = 30;
const int MAXM = 150000;
pair<int,int> f[MAXLOG+1][MAXN][2];
vector<vector<int>> adj;
int n, m;
pair<int,int> pai(pair<int,int> u) {
  int e = 0;
  if (u.second == 1 and (int)adj[u.first].size() > 1) { // já veio de grande
    e = 1;
  }
  int v = adj[u.first][e];
  bool is_v_biggest = false;
  if (adj[v][0] == u.first) is_v_biggest = true;
  return {v, is_v_biggest};
};
pair<int,int> move(pair<int,int> v, int step) {
  for (int b=MAXLOG; b>=0; b--) {
    if ((1 << b) > step) continue;
    step -= (1 << b);
    v = f[b][v.first][v.second];
  }
  return v;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  n = N; m = M;
  adj = vector<vector<int>>(n);
  for (int e=0; e<m; e++) {
    int u = R[e][0], v = R[e][1];
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i=0; i<n; i++) {
    for (int state=0; state<=1; state++) {
      f[0][i][state] = pai({i, state});
    }
  }
  for (int b=1; b<=MAXLOG; b++) {
    for (int i=0; i<n; i++) {
      for (int state=0; state<=1; state++) {
        pair<int,int> mid = f[b-1][i][state];
        f[b][i][state] = f[b-1][mid.first][mid.second];
      }
    }
  }
  for(int g=0; g<Q; g++) {
    int ans = 0;
    for (int i=0; i<n; i++) {
      pair<int,int> dest = move({i, 0}, G[g]);
      if (dest.first == P) {
        ans++;
      }
    }
    answer(ans);
  }
}

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