Submission #1113097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113097		ortsac	Tropical Garden (IOI11_garden)	C++17	69 / 100	5057 ms	85932 KiB

garden

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

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

struct Edge {
  int idx, to;

  Edge(int a = 0, int b = 0) : idx(a), to(b) {}

  bool operator < (const Edge& a) const {
    return (idx < a.idx);
  }
};

const int MAXN = 150010;
const int INF = 0x3f3f3f3f;
const int MAXLOG = 30;
int n, m, p;

vector<Edge> adj[MAXN];
pii nxt[MAXN][2];
pii binl[30][MAXN][2];
int mi[MAXN];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  n = N;
  m = M;
  p = P;
  for (int i = 0; i < n; i++) {
    mi[i] = INF;
  }
  for (int i = 0; i < m; i++) {
    int a = R[i][0], b = R[i][1];
    adj[a].push_back(Edge(i, b));
    adj[b].push_back(Edge(i, a));
    mi[a] = min(mi[a], i);
    mi[b] = min(mi[b], i);
  }
  for (int i = 0; i < n; i++) {
    sort(adj[i].begin(), adj[i].end());
  }
  for (int i = 0; i < n; i++) {
    // faz o do 0
    bool f = 0;
    if (mi[adj[i][0].to] == adj[i][0].idx) f = 1;
    nxt[i][0] = make_pair(adj[i][0].to, f);
    // faz o do 1
    if (((int) adj[i].size()) == 1) {
      nxt[i][1] = nxt[i][0];
    } else {
      f = 0;
      if (mi[adj[i][1].to] == adj[i][1].idx) f = 1;
      nxt[i][1] = make_pair(adj[i][1].to, f);
    }
  }
  // calcular bin lift
  for (int i = 0; i < n; i++) {
    binl[0][i][0] = nxt[i][0];
    binl[0][i][1] = nxt[i][1];
  }
  for (int k = 1; k < MAXLOG; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 2; j++) {
        pii a = binl[k - 1][i][j];
        binl[k][i][j] = binl[k - 1][a.fr][a.se];
      }
    }
  }
  for (int q = 0; q < Q; q++) {
    int k = G[q];
    int ans = 0;
    for (int i = 0; i < n; i++) {
      pii curr = {i, 0};
      for (int b = 0; b < MAXLOG; b++) {
        if (k & (1 << b)) curr = binl[b][curr.fr][curr.se];
      }
      if (curr.fr == p) ans++;
    }
    answer(ans);
  }
}

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