Submission #765999

#	Time	Username	Problem	Language	Result	Execution time	Memory
765999		NeroZein	Tropical Garden (IOI11_garden)	C++17	49 / 100	5076 ms	4872 KiB

garden

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

const int MX = 150005;

int k;
int PP;
int ans;
stack<int> stk;
int vis[MX][2]; 
vector<int> g[MX];

void Dfs (int v, int p, int t) {
  //cout << v << ' '; 
  if (t == k && v == PP) {
    ans++;
    //cout << "GG"; 
    return; 
  }
  if (t > k) return; 
  int nx = (g[v].size() == 1 ? 0 : (p == g[v][0]));
  Dfs(g[v][nx], v, t + 1); 
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  PP = P;   
  for (int i = 0; i < M; ++i) {
    g[R[i][0]].push_back(R[i][1]);
    g[R[i][1]].push_back(R[i][0]);
  }
  k = G[0];
  for (int i = 0; i < N; ++i) {
    Dfs(i, -1, 0); 
    //cout << '\n';
  }
  answer(ans); 
}

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