oj.uz

Submission #299424

# Submission time Handle Problem Language Result Execution time Memory
299424 2020-09-14T21:52:22 Z Haunted_Cpp Tropical Garden (IOI11_garden) C++17
49 / 100
 158 ms 55552 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 350'000 + 5;
const int MAX_M = 350'000 + 5;
const int MAX_K = 32;

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();
  for (int i = 0; i < N; i++) {
    if (!vis[i]) {
      build_graph(0, true);
    }
  }
  vis.reset();
  for (int i = 0; i < N; i++) {
    if (!vis[i]) {
      build_graph(0, 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, 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
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 55288 KB Output is correct
2 Correct 157 ms 55288 KB Output is correct
3 Correct 156 ms 55416 KB Output is correct
4 Correct 151 ms 55160 KB Output is correct
5 Correct 153 ms 55288 KB Output is correct
6 Correct 152 ms 55288 KB Output is correct
7 Correct 157 ms 55288 KB Output is correct
8 Correct 156 ms 55408 KB Output is correct
9 Correct 158 ms 55552 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 55288 KB Output is correct
2 Correct 157 ms 55288 KB Output is correct
3 Correct 156 ms 55416 KB Output is correct
4 Correct 151 ms 55160 KB Output is correct
5 Correct 153 ms 55288 KB Output is correct
6 Correct 152 ms 55288 KB Output is correct
7 Correct 157 ms 55288 KB Output is correct
8 Correct 156 ms 55408 KB Output is correct
9 Correct 158 ms 55552 KB Output is correct
10 Incorrect 155 ms 55240 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 55288 KB Output is correct
2 Correct 157 ms 55288 KB Output is correct
3 Correct 156 ms 55416 KB Output is correct
4 Correct 151 ms 55160 KB Output is correct
5 Correct 153 ms 55288 KB Output is correct
6 Correct 152 ms 55288 KB Output is correct
7 Correct 157 ms 55288 KB Output is correct
8 Correct 156 ms 55408 KB Output is correct
9 Correct 158 ms 55552 KB Output is correct
10 Incorrect 155 ms 55240 KB Output isn't correct
11 Halted 0 ms 0 KB -