#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
#define rep0(kk, l1, l2)for(ll kk = l1; kk < l2; kk++)
#define rep1(kk, l1, l2)for(ll kk = l1; kk <= l2; kk++)
#define foritr(itr, A) for(set<ll>::iterator itr = A.begin(); itr != A.end(); itr++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define cr(x) cerr << #x << " = " << x << "\n";
#define crA(x, A) cerr << #x << " = " << A[x] << "\n";
#define spacing if(db)cout << " ";
#define mmst(x, v) memset((x), v, sizeof ((x)));
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, m, ep, leader[MAXN],co;
vector <ll> v[MAXN], g[MAXN];
ll node[MAXN][2];
vector <pi> edges;
void connect(ll a, ll b)
{
bool best = (v[a][0] == b);
if(best)
{
// put node (a, 0)
if(v[b].size() == 1 && v[b][0] == a)
{
// put node(b, 1&0);
g[node[a][0]].pb(node[b][0]);
// g[node[a][0]].pb(node[b][1]);
}
else if(v[b][0] == a)
{
// this edge is his best
// put node(b, 1)
g[node[a][0]].pb(node[b][1]);
}
else if(v[b][1] == a)
{
// can put
// node(b, 0)
g[node[a][0]].pb(node[b][0]);
}
}
if(!best && b == v[a][1])
{
// put node (a, 1)
// put node (a, 0)
if(v[b].size() == 1 && v[b][0] == a)
{
// put node(b, 1&0);
g[node[a][1]].pb(node[b][0]);
// g[node[a][1]].pb(node[b][1]);
}
else if(v[b][0] == a)
{
// this edge is his best
// put node(b, 1)
g[node[a][1]].pb(node[b][1]);
}
else if(v[b][1] == a)
{
// can put
// node(b, 0)
g[node[a][1]].pb(node[b][0]);
}
}
}
void transverse()
{
FOR(i,0,MAXN) v[i].clear();
FOR(i,0,MAXN)
{
assert(g[i].size() <= 1);
for(auto j : g[i])
{
v[j].pb(i);
}
}
FOR(i,0,MAXN) g[i].clear();
}
ll dist[MAXN],len;
bool cycle;
void dfs(ll x) // after splitting, there exists only one out-going edge
{
if(cycle) return;
assert(v[x].size() <= 1);
for(auto i : v[x])
{
if(cycle) break;
if(dist[i] != -1 && cycle == 0)
{
cycle = 1; assert(dist[i] == 0);
len = dist[x] + 1;
break;
}
dist[i] = dist[x] + 1;
dfs(i);
}
if(cycle) return;
}
ll answer_queries[2006];
map <pi, bool> mp;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N, m = M, ep = P;
FOR(i, 0, n) {node[i][0] = co ++; node[i][1] = co ++;}
FOR(i, 0, m)
{
ll a = R[i][0], b = R[i][1]; bool can = 0;
if(v[a].size() < 2) can=1,v[a].pb(b);
if(v[b].size() < 2) can=1,v[b].pb(a);
if(can) edges.pb(pi(a, b));
}
for(auto i : edges)
{
ll a = i.f, b = i.s;
connect(a, b);
connect(b, a);
}
assert(co == n*2);
transverse();
mmst(dist, -1);
dist[node[ep][0]] = 0;
dfs(node[ep][0]);
if(cycle)
{
FOR(i,0,co)
{
if(dist[i] == -1) continue;
assert(dist[i] < len);
FOR(j,0,Q)
{
if(dist[i] == G[j]%len && !mp[pi(j, i/2)])
{
mp[pi(j, i/2)] = 1;
answer_queries[j] ++;
}
}
}
}
else
{
FOR(i,0,co)
{
if(dist[i] == -1) continue;
// assert(dist[i] < len);
FOR(j,0,Q)
{
if(dist[i] == G[j] && !mp[pi(j, i/2)])
{
mp[pi(j, i/2)] = 1;
answer_queries[j] ++;
}
}
}
}
cycle = 0, len = 0;
mmst(dist, -1);
dist[node[ep][1]] = 0;
dfs(node[ep][1]);
if(cycle)
{
FOR(i,0,co)
{
if(dist[i] == -1) continue;
assert(dist[i] < len);
FOR(j,0,Q)
{
if(dist[i] == G[j]%len && !mp[pi(j, i/2)])
{
mp[pi(j, i/2)] = 1;
answer_queries[j] ++;
}
}
}
}
else
{
FOR(i,0,co)
{
if(dist[i] == -1) continue;
// assert(dist[i] < len);
FOR(j,0,Q)
{
if(dist[i] == G[j] && !mp[pi(j, i/2)])
{
mp[pi(j, i/2)] = 1;
answer_queries[j] ++;
}
}
}
}
FOR(i,0,Q) answer(answer_queries[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
