#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
/*****************************************/
//just have to implement
#define pi pair<int,int>
#define pb push_back
#define ll long long
#define f first
#define s second
const int maxn = 1e3 +5;
//int level[maxn];
set<pi> graph[maxn];
ll bfs(int n, int k){
queue<tuple<int,int,int>> bfsq;//curnode, parent, level
//for(pi adj : graph[n]){
//bfsq.push({adj.f, n, 1 });
//}
bfsq.push({n,-1, 0});
ll ans = 0;
//cout << k <<":\n\n";
while(bfsq.size()){
int node, parent, level;
tie(node, parent,level) = bfsq.front();
bfsq.pop();
if(level > k) continue;
if(graph[node].begin()->s != parent && parent != -1 ){
if(graph[node].size()>1 && next(graph[node].begin())->s == parent )
bfsq.push({next(graph[node].begin())->s, node, level + 1});
continue;
}
//cout << node <<", "<<parent<<", "<<level<<"\n";
if(level == k)
{
//cout <<"YES\n";
ans++;
continue;
}
// if(graph[node].size() == 1){
// bfsq.push({graph[node].begin()->s, node, level +1});
//continue;
//}
for(pi adj : graph[node]){
auto fadj = graph[adj.s].begin();
if(fadj->s == node){
bfsq.push({adj.s, node, level +1});
//cout << level<<": "<<node <<"->"<<adj.s<<'\n';
}
else if(graph[adj.s].size() > 1 && next(fadj)->s == node){
bfsq.push({fadj->s, adj.s, level + 2 });
//cout << level<<"+: "<<node <<"->"<<adj.s<<"->"<<fadj->s<<'\n';
}
}
}
return ans;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i =0; i<M; i++){
graph[R[i][0]].insert({i,R[i][1] });
graph[R[i][1]].insert({i,R[i][0]});
}
for(int i =0; i<Q; i++){
ll res = bfs(P, G[i]);
answer(res);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1129 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1129 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1129 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |