Submission #299420

#	Time	Username	Problem	Language	Result	Execution time	Memory
299420		Haunted_Cpp	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	130 ms	41600 KiB

garden

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

const int MAX_N = 150'000 + 5;
const int MAX_M = 300'000 + 5;
const int MAX_K = 31;

int dp[MAX_M][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] = (dead_end[node] ? _N + second[node] : second[node]);
    } else {
      dp[_N + node][0] = (dead_end[node] ? _N + second[node] : _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();
  build_graph(0, true);
  vis.reset();
  build_graph(0, false);
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 0; i < MAX_M; i++) {
      dp[i][j] = dp[dp[i][j - 1]][j - 1];
    }
  }
  auto kth = [&](int node, int k) -> int {
    for (int 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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31