oj.uz

Submission #650012

# Submission time Handle Problem Language Result Execution time Memory
650012 2022-10-11T21:00:09 Z alvinpiter Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 5044 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 150000

int P;
vector<pair<int, int> > adj[MAXN + 3];

bool check(int u, int stepsLeft, int prevBeauty) {
  if (stepsLeft == 0) {
    return u == P;
  }

  int nextEdgeIdx = -1;
  for (int i = 0; i < adj[u].size(); i++) {
    auto [v, beauty] = adj[u][i];
    if (beauty != prevBeauty) {
      if (nextEdgeIdx == -1 || beauty < adj[u][nextEdgeIdx].second) {
        nextEdgeIdx = i;
      }
    }
  }

  // If there is no other edge, take the last edge, which must be indexed 0.
  if (nextEdgeIdx == -1) {
    nextEdgeIdx = 0;
  }

  return check(adj[u][nextEdgeIdx].first, stepsLeft - 1, adj[u][nextEdgeIdx].second);
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
  P = p;

  for (int i = 0; i < m; i++) {
    adj[r[i][0]].push_back({r[i][1], i});
    adj[r[i][1]].push_back({r[i][0], i});
  }

  for (int i = 0; i < q; i++) {
    int ans = 0;
    for (int startingFountain = 0; startingFountain < n; startingFountain++) {
      ans += check(startingFountain, g[i], -1);
    }

    answer(ans);
  }
}

Compilation message

garden.cpp: In function 'bool check(int, int, int)':
garden.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int i = 0; i < adj[u].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3832 KB Output is correct
2 Correct 3 ms 3884 KB Output is correct
3 Correct 3 ms 3844 KB Output is correct
4 Correct 2 ms 3832 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 3924 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 5 ms 3832 KB Output is correct
9 Correct 11 ms 4204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3832 KB Output is correct
2 Correct 3 ms 3884 KB Output is correct
3 Correct 3 ms 3844 KB Output is correct
4 Correct 2 ms 3832 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 3924 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 5 ms 3832 KB Output is correct
9 Correct 11 ms 4204 KB Output is correct
10 Correct 11 ms 3796 KB Output is correct
11 Execution timed out 5038 ms 5044 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3832 KB Output is correct
2 Correct 3 ms 3884 KB Output is correct
3 Correct 3 ms 3844 KB Output is correct
4 Correct 2 ms 3832 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 3924 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 5 ms 3832 KB Output is correct
9 Correct 11 ms 4204 KB Output is correct
10 Correct 11 ms 3796 KB Output is correct
11 Execution timed out 5038 ms 5044 KB Time limit exceeded
12 Halted 0 ms 0 KB -