Submission #1262390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262390		kawhiet	Tropical Garden (IOI11_garden)	C++20	49 / 100	5099 ms	165832 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

int k, t, res = 0;
vector<vector<pair<int, int>>> g;

void dfs(int u, int p, int d = 0) {
  if (d == k) {
    res += (u == t);
    return;
  }
  int i = p;
  vector<pair<int, int>> a;
  for (auto [v, w] : g[u]) {
    a.push_back({w, v});
  }
  sort(a.begin(), a.end());
  if (a.size() == 1) {
    dfs(a[0].second, u, d + 1);
  }
  else {
    if (a[0].second == p) {
      dfs(a[1].second, u, d + 1);
    }
    else {
      dfs(a[0].second, u, d + 1);
    }
  }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  t = P;
  g.resize(N);
  for (int i = 0; i < M; i++) {
    int u = R[i][0], v = R[i][1];
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  for (int q = 0; q < Q; q++) {
    res = 0;
    k = G[q];
    for (int i = 0; i < N; i++) {
      dfs(i, -1);
    }
    answer(res);
  }
}

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31