Submission #1307780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307780		orgiloogii	Tropical Garden (IOI11_garden)	C++20	49 / 100	5094 ms	1604 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> adj;
int n, m, goal, q;
int ans = 0;

void solve(int cnt, int p, int u) {
  //  cout << cnt << " " << p << " " << u << " " << goal << endl;
    if (cnt == q && u != goal) {
        return;
    }
    else if (cnt == q && u == goal) {
        ans++;
        return;
    }
   for (auto v : adj[u]) {
        if (v == p && adj[u].size() == 2) continue;
        solve(cnt + 1, u, v);
        break;
   }
   return;
}

void count_routes(int N, int M, int P, int r[][2], int Q, int g[]) {
    n = N;
    adj.resize(n);
    m = M;
    goal = P;
    for (int i = 0;i < m;i++) {
        int u = r[i][0];
        int v = r[i][1];
        if (adj[u].size() < 2) adj[u].push_back(v);
        if (adj[v].size() < 2) adj[v].push_back(u);
    }
    for(int i = 0; i < Q; i++) {
        q = g[i];
        int ans = 0;
        for (int i = 0;i < n;i++) {
            solve(0, -1, i);
        }
        //answer(ans);
    }
    answer(ans);
}
/*int main() {
    int r[6][2];
    r[0][0] = 1;
    r[0][1] = 2;
    r[1][0] = 0;
    r[1][1] = 1;
    r[2][0] = 0;
    r[2][1] = 3;
    r[3][0] = 3;
    r[3][1] = 4;
    r[4][0] = 4;
    r[4][1] = 5;
    r[5][0] = 1;
    r[5][1] = 5;
    int q[1];
    q[0] = 3;
    count_routes(6, 6, 0, r, 1, q);
}*/

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