Submission #299431

#	Time	Username	Problem	Language	Result	Execution time	Memory
299431		Haunted_Cpp	Tropical Garden (IOI11_garden)	C++17	69 / 100	5009 ms	60536 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 300'000 + 5;
//~ const int MAX_M = 600'000 + 5;
const int MAX_K = 35;

int dp[MAX_N][MAX_K];

vector<vector<pair<int, int>>> g(MAX_N);

int _N;

vector<int> minimum(MAX_N);
vector<int> second(MAX_N);

bitset<MAX_N> vis;
//~ bitset<MAX_N> dead_end;

void build_graph(int node, bool fill_min) {
  vis[node] = true;
  if (fill_min) {
    pair<int, int> mn = {1e9, 1e9};
    pair<int, int> second_best = {1e9, 1e9};
    //~ int cnt = 0;
    for (auto &[to, w] : g[node]) {
      //~ ++cnt;
      if (make_pair(w, to) <= mn) {
        swap(mn, second_best);
        mn = {w, to};
      } else {
        second_best = min(second_best, {w, to});
      }
    }
    if (second_best == make_pair((int) 1e9, (int) 1e9)) {
      second_best = mn;
    }
    //~ dead_end[node] = (cnt == 1);
    second[node] = second_best.second;
    minimum[node] = mn.second;
  } else {
    if (node != minimum[minimum[node]]) {
      // NORMAL
      dp[node][0] = minimum[node];
    } else {
      // NORMAL -> SPECIAL 
      dp[node][0] = _N + minimum[node];
    }
    if (minimum[second[node]] != node) {
      dp[_N + node][0] = second[node];
    } else {
      dp[_N + node][0] = _N + second[node];
    }
  }
  for (auto &[to, w] : g[node]) {
    if (!vis[to]) {
      vis[to] = true;
      build_graph(to, fill_min);
    }
  }
}

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++) {
    g[R[i][0]].emplace_back(R[i][1], i);
    g[R[i][1]].emplace_back(R[i][0], i);
  }
  vis.reset();
  int comp = 0;
  for (int i = 0; i < N; i++) {
    if (!vis[i]) {
      ++comp;
      build_graph(i, true);
    }
  }
  vis.reset();
  for (int i = 0; i < N; i++) {
    if (!vis[i]) {
      build_graph(i, false);
    }
  }
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 0; i < MAX_N; i++) {
      dp[i][j] = dp[dp[i][j - 1]][j - 1];
    }
  }
  auto kth = [&](int node, long long k) -> int {
    for (long long i = 0; i < MAX_K; i++) {
      if ((k >> i) & 1) {
        node = dp[node][i];
      }
    }
    int A = node;
    int B = node - N;
    return (B >= 0 ? B : A);
  };
  for (int i = 0; i < Q; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++) {
      cnt += (kth(j, G[i]) == P);
    }
    answer(cnt);
  }
}

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