Submission #1304960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304960		nicolo_010	Tropical Garden (IOI11_garden)	C++20	49 / 100	5092 ms	1600 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<vector<int>> adj;
int k;
int e;
int cnt=0;


void dfs(int n, int p, int d) {
    //cout << n << " " << p << " " << d << " " << e << endl;
    if (d==k) {
        cnt += (n==e);
        return;
    }
    for (auto x : adj[n]) {
        if (x==p && adj[n].size()>1) continue;
        dfs(x, n, d+1);
        break;
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    int n = N, m = M;
    e = P;
    adj.assign(n, {});
    for (int i=0; i<m; i++) {
        int a = R[i][0];
        int b = R[i][1];
        if (adj[a].size()<2) adj[a].push_back(b);
        if (adj[b].size()<2) adj[b].push_back(a);
    }
    for (int i=0; i<Q; i++) {
        cnt=0;
        for (int j=0; j<n; j++) {
            k=G[i];
            //cout << "PATH OF " << j << ": " << endl;
            dfs(adj[j][0], j, 1);
        }
        answer(cnt);
    }
}

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