oj.uz

Submission #299431

# Submission time Handle Problem Language Result Execution time Memory
299431 2020-09-14T22:19:07 Z Haunted_Cpp Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 60536 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 50936 KB Output is correct
2 Correct 154 ms 50944 KB Output is correct
3 Correct 154 ms 50944 KB Output is correct
4 Correct 153 ms 50936 KB Output is correct
5 Correct 155 ms 50808 KB Output is correct
6 Correct 189 ms 51064 KB Output is correct
7 Correct 153 ms 50808 KB Output is correct
8 Correct 198 ms 50936 KB Output is correct
9 Correct 160 ms 51320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 50936 KB Output is correct
2 Correct 154 ms 50944 KB Output is correct
3 Correct 154 ms 50944 KB Output is correct
4 Correct 153 ms 50936 KB Output is correct
5 Correct 155 ms 50808 KB Output is correct
6 Correct 189 ms 51064 KB Output is correct
7 Correct 153 ms 50808 KB Output is correct
8 Correct 198 ms 50936 KB Output is correct
9 Correct 160 ms 51320 KB Output is correct
10 Correct 159 ms 50936 KB Output is correct
11 Correct 168 ms 52440 KB Output is correct
12 Correct 192 ms 54520 KB Output is correct
13 Correct 230 ms 60536 KB Output is correct
14 Correct 312 ms 59896 KB Output is correct
15 Correct 301 ms 60536 KB Output is correct
16 Correct 271 ms 60536 KB Output is correct
17 Correct 252 ms 60536 KB Output is correct
18 Correct 186 ms 54648 KB Output is correct
19 Correct 298 ms 59768 KB Output is correct
20 Correct 299 ms 60408 KB Output is correct
21 Correct 271 ms 60536 KB Output is correct
22 Correct 253 ms 60280 KB Output is correct
23 Correct 321 ms 60024 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 50936 KB Output is correct
2 Correct 154 ms 50944 KB Output is correct
3 Correct 154 ms 50944 KB Output is correct
4 Correct 153 ms 50936 KB Output is correct
5 Correct 155 ms 50808 KB Output is correct
6 Correct 189 ms 51064 KB Output is correct
7 Correct 153 ms 50808 KB Output is correct
8 Correct 198 ms 50936 KB Output is correct
9 Correct 160 ms 51320 KB Output is correct
10 Correct 159 ms 50936 KB Output is correct
11 Correct 168 ms 52440 KB Output is correct
12 Correct 192 ms 54520 KB Output is correct
13 Correct 230 ms 60536 KB Output is correct
14 Correct 312 ms 59896 KB Output is correct
15 Correct 301 ms 60536 KB Output is correct
16 Correct 271 ms 60536 KB Output is correct
17 Correct 252 ms 60536 KB Output is correct
18 Correct 186 ms 54648 KB Output is correct
19 Correct 298 ms 59768 KB Output is correct
20 Correct 299 ms 60408 KB Output is correct
21 Correct 271 ms 60536 KB Output is correct
22 Correct 253 ms 60280 KB Output is correct
23 Correct 321 ms 60024 KB Output is correct
24 Correct 166 ms 51064 KB Output is correct
25 Execution timed out 5009 ms 52472 KB Time limit exceeded
26 Halted 0 ms 0 KB -