oj.uz

Submission #304698

# Submission time Handle Problem Language Result Execution time Memory
304698 2020-09-21T17:37:10 Z AlexPop28 Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 49144 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
  vector<vector<int>> to(n);
  for (int i = 0; i < m; ++i) {
    int a = r[i][0], b = r[i][1];
    if ((int)to[a].size() < 2) to[a].emplace_back(b);
    if ((int)to[b].size() < 2) to[b].emplace_back(a);
  }
  
  vector<int> nxt(2 * n, -1);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 2 && j < (int)to[i].size(); ++j) {
      int x = to[i][j];
      int node = (to[x][0] == i) * n + x;
      nxt[j * n + i] = node;
    }
  }
  for (int i = n; i < 2 * n; ++i) if (nxt[i] == -1) nxt[i] = nxt[i - n];
  
  vector<vector<int>> jump(30, vector<int>(2 * n));
  jump[0] = nxt;
  for (int i = 1; i < 30; ++i) {
    for (int j = 0; j < 2 * n; ++j) {
      jump[i][j] = jump[i - 1][jump[i - 1][j]];
    }
  }
  
  vector<int> pos(n);
  for (int it = 0; it < q; ++it) {
    int k = qrs[it];
    iota(pos.begin(), pos.end(), 0);
    
    for (int bit = 0; k; ++bit) {
      if (!(k & (1 << bit))) continue;
      k ^= 1 << bit;
      for (int i = 0; i < n; ++i) {
        pos[i] = jump[bit][pos[i]];
      }
    }
    
    int ans = count(pos.begin(), pos.end(), p) + 
              count(pos.begin(), pos.end(), n + p);
    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 572 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 572 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 15 ms 7680 KB Output is correct
12 Correct 31 ms 12920 KB Output is correct
13 Correct 59 ms 28152 KB Output is correct
14 Correct 112 ms 44408 KB Output is correct
15 Correct 121 ms 44920 KB Output is correct
16 Correct 88 ms 30968 KB Output is correct
17 Correct 83 ms 26360 KB Output is correct
18 Correct 32 ms 12920 KB Output is correct
19 Correct 112 ms 44408 KB Output is correct
20 Correct 114 ms 44920 KB Output is correct
21 Correct 85 ms 30968 KB Output is correct
22 Correct 78 ms 26488 KB Output is correct
23 Correct 122 ms 49144 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 572 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 15 ms 7680 KB Output is correct
12 Correct 31 ms 12920 KB Output is correct
13 Correct 59 ms 28152 KB Output is correct
14 Correct 112 ms 44408 KB Output is correct
15 Correct 121 ms 44920 KB Output is correct
16 Correct 88 ms 30968 KB Output is correct
17 Correct 83 ms 26360 KB Output is correct
18 Correct 32 ms 12920 KB Output is correct
19 Correct 112 ms 44408 KB Output is correct
20 Correct 114 ms 44920 KB Output is correct
21 Correct 85 ms 30968 KB Output is correct
22 Correct 78 ms 26488 KB Output is correct
23 Correct 122 ms 49144 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 479 ms 7752 KB Output is correct
26 Correct 872 ms 13176 KB Output is correct
27 Correct 2386 ms 28152 KB Output is correct
28 Correct 4179 ms 44408 KB Output is correct
29 Correct 4118 ms 45048 KB Output is correct
30 Correct 2765 ms 30968 KB Output is correct
31 Correct 2226 ms 26360 KB Output is correct
32 Correct 896 ms 12920 KB Output is correct
33 Correct 4108 ms 44408 KB Output is correct
34 Correct 4222 ms 45016 KB Output is correct
35 Correct 3148 ms 30968 KB Output is correct
36 Correct 2621 ms 26488 KB Output is correct
37 Execution timed out 5098 ms 49144 KB Time limit exceeded