oj.uz

Submission #837001

# Submission time Handle Problem Language Result Execution time Memory
837001 2023-08-24T19:34:18 Z thimote75 Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 2080 KB 
#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

igrid roads;

int createNode (int node, bool cMax) {
  return 2 * node + (cMax ? 1 : 0);
}

idata functional_graph;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  roads.resize(N);

  for (int i = M - 1; i >= 0; i --) {
    roads[R[i][0]].push_back(R[i][1]);
    roads[R[i][1]].push_back(R[i][0]);
  }

  functional_graph.resize(2 * N);
  for (int i = 0; i < N; i ++) {
    idata &l_roads = roads[i];

    int nmax = l_roads[l_roads.size() - 1];
    int nmix = l_roads[max(0, (int) l_roads.size() - 2)];
    
    functional_graph[2 * i]     = 2 * nmax + (roads[nmax][roads[nmax].size() - 1] == i ? 1 : 0);
    functional_graph[2 * i + 1] = 2 * nmix + (roads[nmix][roads[nmix].size() - 1] == i ? 1 : 0);
  }

  for (int i = 0; i < Q; i ++) {
    int duration = G[i];
    int count    = 0;
    for (int j = 0; j < N; j ++) {
      int x = 2 * j;

      for (int t = 0; t < duration; t ++)
        x = functional_graph[x];

      if (x == 2 * P || x == 2 * P + 1) count ++;
    }

    answer(count);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Execution timed out 5053 ms 2080 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Execution timed out 5053 ms 2080 KB Time limit exceeded
12 Halted 0 ms 0 KB -