#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
struct graph
{
int n;
int h;
vector<vector<int>> adjlist;
vector<vector<int>> best;
vector<int> dist;
vector<bool> cycle;
int cyc = 2e9;
int p;
void add(int fr, int to)
{
int t = to;
if (fr == best[to][0]) t += h;
if (best[fr][0] == to)
{
adjlist[fr].push_back(t);
}
if (best[fr][1] == to)
{
adjlist[fr + h].push_back(t);
}
}
graph(int in, int m, vector<vector<int>> ib, int R[][2]) : n(2*in), h(in), adjlist(vector<vector<int>>(2*n)), best(ib), dist(n, -1), cycle(n)
{
for (int i = 0; i < m; i++)
{
add(R[i][0], R[i][1]);
add(R[i][1], R[i][0]);
}
}
void print()
{
cout << n << "\n";
for (int i = 0; i < n; i++)
{
for (auto j : adjlist[i])
{
cout << i << " " << j << "\n";
}
}
}
void reverse()
{
vector<vector<int>> old(n);
swap(old, adjlist);
for (int i = 0; i < n; i++)
{
for (int j : old[i])
{
adjlist[j].push_back(i);
}
}
}
bool dfs(int curr, int d)
{
if (curr == p && dist[curr] != -1)
{
cyc = d;
return true;
}
dist[curr] = d;
for (auto next : adjlist[curr])
{
if (dfs(next, d + 1)) cycle[curr] = true;
}
return cycle[curr];
}
void calc(int P)
{
p = P;
dfs(p, 0);
}
void pcyc()
{
cout << "Cycle: " << cyc << "\n";
for (int i = 0; i < n; i++)
{
cout << (i % h);
if (i >= h) cout << "*";
else cout << " ";
cout << ": ";
cout << cycle[i] << " " << dist[i] << "\n";
}
}
map<int,vector<int>> lkup;
void precheck()
{
for (int i = 0; i < h; i++)
{
lkup[dist[i] % cyc].push_back(dist[i]);
}
for (auto& p : lkup)
{
sort(p.second.begin(), p.second.end());
}
}
int check(int t)
{
int tm = t % cyc;
return lkup[tm].end() - lower_bound(lkup[tm].begin(), lkup[tm].end(), t);
}
};
void count_routes(int n, int m, int P, int R[][2], int Q, int G[])
{
vector<vector<int>> best(n, vector<int>(2, -1));
auto ins = [&](int k, int v)
{
swap(best[k][0], best[k][1]);
best[k][0] = v;
};
for (int i = m - 1; i >= 0; i--)
{
ins(R[i][0], R[i][1]);
ins(R[i][1], R[i][0]);
}
for (int i = 0; i < n; i++) if (best[i][1] == -1) best[i][1] = best[i][0];
graph g(n, m, best, R);
g.reverse();
graph g2(g);
g.calc(P);
g2.calc(P + n);
g.precheck();
g2.precheck();
for (int c = 0; c < Q; c++)
{
answer(g.check(G[c]) + g2.check(G[c]));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
