oj.uz

Submission #363383

# Submission time Handle Problem Language Result Execution time Memory
363383 2021-02-05T18:43:50 Z WLZ Tropical Garden (IOI11_garden) C++14
100 / 100
 3016 ms 43504 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int bfs(int s, const vector< vector<int> > &g, vector<int> &dist) {
  int n = (int) g.size();
  dist.assign(n, -1); dist[s] = 0;
  queue<int> q; q.push(s);
  int c = -1;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (auto& v : g[u]) {
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q.push(v);
      }
      if (v == s) {
        c = dist[u] + 1;
      }
    }
  }
  return c;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  vector< set<int> > mn(N);
  for (int i = 0; i < M; i++) {
    mn[R[i][0]].insert(i);
    mn[R[i][1]].insert(i);
  }
  vector< vector<int> > g(2 * N);
  for (int i = 0; i < N; i++) {
    int idx = *mn[i].begin();
    int other = R[idx][0];
    if (other == i) other = R[idx][1];
    if (idx == *mn[other].begin() && (int) mn[other].size() > 1) g[2 * other + 1].push_back(2 * i);
    else g[2 * other].push_back(2 * i);
    if ((int) mn[i].size() == 1) continue;
    idx = *next(mn[i].begin());
    other = R[idx][0];
    if (other == i) other = R[idx][1];
    if (idx == *mn[other].begin() && (int) mn[other].size() > 1) g[2 * other + 1].push_back(2 * i + 1);
    else g[2 * other].push_back(2 * i + 1);
  }
  vector<int> dist1, dist2;
  int c1 = bfs(2 * P, g, dist1);
  int c2 = bfs(2 * P + 1, g, dist2);
  for (int i = 0; i < Q; i++) {
    int cnt = 0;
    for (int u = 0; u < 2 * N; u += 2) {
      bool b1 = dist1[u] != -1;
      if (c1 == -1) b1 = b1 && dist1[u] == G[i];
      else b1 = b1 && dist1[u] <= G[i] && (G[i] - dist1[u]) % c1 == 0;
      bool b2 = dist2[u] != -1;
      if (c2 == -1) b2 = b2 && dist2[u] == G[i];
      else b2 = b2 && dist2[u] <= G[i] && (G[i] - dist2[u]) % c2 == 0;
      if (b1 || b2) cnt++;
    }
    answer(cnt);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 5 ms 1388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 5 ms 1388 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 16 ms 6252 KB Output is correct
12 Correct 53 ms 11756 KB Output is correct
13 Correct 61 ms 24684 KB Output is correct
14 Correct 214 ms 35732 KB Output is correct
15 Correct 247 ms 36716 KB Output is correct
16 Correct 219 ms 29192 KB Output is correct
17 Correct 204 ms 27028 KB Output is correct
18 Correct 51 ms 11756 KB Output is correct
19 Correct 202 ms 35692 KB Output is correct
20 Correct 249 ms 36716 KB Output is correct
21 Correct 239 ms 29292 KB Output is correct
22 Correct 230 ms 27116 KB Output is correct
23 Correct 205 ms 38764 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 5 ms 1388 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 16 ms 6252 KB Output is correct
12 Correct 53 ms 11756 KB Output is correct
13 Correct 61 ms 24684 KB Output is correct
14 Correct 214 ms 35732 KB Output is correct
15 Correct 247 ms 36716 KB Output is correct
16 Correct 219 ms 29192 KB Output is correct
17 Correct 204 ms 27028 KB Output is correct
18 Correct 51 ms 11756 KB Output is correct
19 Correct 202 ms 35692 KB Output is correct
20 Correct 249 ms 36716 KB Output is correct
21 Correct 239 ms 29292 KB Output is correct
22 Correct 230 ms 27116 KB Output is correct
23 Correct 205 ms 38764 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 192 ms 6252 KB Output is correct
26 Correct 261 ms 11884 KB Output is correct
27 Correct 2531 ms 24892 KB Output is correct
28 Correct 1469 ms 36076 KB Output is correct
29 Correct 3000 ms 36844 KB Output is correct
30 Correct 1733 ms 29292 KB Output is correct
31 Correct 1791 ms 27372 KB Output is correct
32 Correct 279 ms 11956 KB Output is correct
33 Correct 1489 ms 35820 KB Output is correct
34 Correct 3016 ms 36820 KB Output is correct
35 Correct 1858 ms 29316 KB Output is correct
36 Correct 1812 ms 27372 KB Output is correct
37 Correct 1253 ms 38940 KB Output is correct
38 Correct 2320 ms 43504 KB Output is correct