Submission #650012

#	Time	Username	Problem	Language	Result	Execution time	Memory
650012		alvinpiter	Tropical Garden (IOI11_garden)	C++17	49 / 100	5038 ms	5044 KiB

garden

#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 (stderr)

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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31