Submission #1035180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035180		vjudge1	Tropical Garden (IOI11_garden)	C11	100 / 100	1780 ms	9320 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <stdbool.h>
#include <string.h>
#include <assert.h>

int dsu_find(int *par, int a) {
  return par[a] < 0 ? a : (par[a] = dsu_find(par, par[a]));
}

void dsu_union(int *par, int a, int b) {
  a = dsu_find(par, a);
  b = dsu_find(par, b);
  assert(a != b); // we should only call dsu_union if they belong to different components
  if (-par[b] > -par[a]) {
    int tmp = a;
    a = b;
    b = tmp;
  }
  par[a] += par[b];
  par[b] = a;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  static int most_beautiful[150001][2];
  static int graph[300001];
  static int dsu[300001];
  static int rem[2][300001];
  int cyc[2];
  cyc[0] = cyc[1] = 1e9 + 1;
  memset(dsu, -1, sizeof dsu[0] * (2 * (size_t)N + 1));
  assert(dsu[2 * N] == -1);
  // 1 indexing, graph[u] == 0, means no edges connected to it
  P++;

  // save 2 most_beautiful edges
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < 2; j++) {
      int u = R[i][j] + 1;
      int v = R[i][j^1] + 1;
      if (most_beautiful[u][0] == 0) {
        most_beautiful[u][0] = v;
      } else if (most_beautiful[u][1] == 0) {
        most_beautiful[u][1] = v;
      }
    }
  }

  // build functional graph
  for (int u = 1; u <= N; u++) {
    for (int j = 0; j < 2; j++) {
      int v = most_beautiful[u][j];
      if (most_beautiful[v][0] != u || most_beautiful[v][1] == 0)
        graph[u + j*N] = v;
      else
        graph[u + j*N] = v + N;
    }
  }

  // set everything in cycle
  for (int u = 1; u <= 2 * N; u++) {
    if (graph[u] == 0) continue;
    if (dsu_find(dsu, u) != dsu_find(dsu, graph[u])) {
      dsu_union(dsu, u, graph[u]);
      continue;
    }
    bool seen[2] = {false};
    int c = 0;
    int v = u;
    do {
      v = graph[v];
      seen[0] = seen[0] || v == P;
      seen[1] = seen[1] || v == P + N;
      rem[0][v] = rem[1][v] = -1;
      c++;
    } while (v != u);

    for (int i = 0; i < 2; i++) {
      if (!seen[i]) continue;
      cyc[i] = c;
      v = graph[P + i * N];
      for (int j = 1; j <= c; j++) {
        rem[i][v] = c - j;
        v = graph[v];
      }
      assert(v == graph[P + i * N]);
    }
  }
  
  // set everything out of cycle
  for (int i = 0; i < 2; i++) {
    int target = P + i * N;
    for (int u = 1; u <= N; u++) {
      if (rem[i][u] != 0 || u == target) continue;

      int v = u;
      int d = 0;
      do {
        rem[i][v] = -1;
        d++;
        v = graph[v];
      } while (rem[i][v] == 0 && v != target);

      if (v == target) {
        assert(rem[i][target] == -1 || rem[i][target] == 0);
        for (v = u; v != graph[target]; v = graph[v])
          rem[i][v] = d--;
        assert(d == -1);
        assert(rem[i][target] == 0);
      } else if (rem[i][v] > 0) {
        for (int w = u; w != v; w = graph[w])
          rem[i][w] = rem[i][v] + d--;
        assert(d == 0);
      }
    }
  }
  
  for (int i = 0; i < Q; i++) {
    int res = 0;
    for (int j = 0; j < 2; j++) {
      for (int k = 1; k <= N; k++) {
        if (rem[j][k] == -1) continue;
        res += rem[j][k] <= G[i] && (G[i] - rem[j][k]) % cyc[j] == 0;
      }
    }
    answer(res);
  }
}

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