#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
namespace Wrap
{
#define SZ 666666
int n,m,N,p,a[SZ],b[SZ],u[SZ];
int gb(int e,int t)
{return a[e]^b[e]^t;}
vector<int> e[SZ],pre[SZ];
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
struct Sup
{
vector<int> v[SZ];
int GA;
map<int,vector<int> > sb;
void init(int x)
{
queue<pii> q;
q.push(pii(x,0));
while(!q.empty())
{
pii w=q.front(); q.pop();
if(v[w.fi].size()>2) continue;
v[w.fi].pb(w.se);
for(auto g:pre[w.fi])
q.push(pii(g,w.se+1));
}
GA=-1;
for(int i=0;i<N;++i) if(v[i].size()&&i%2==0)
{
int G=(v[i].size()==2)?(v[i][1]-v[i][0]):(1.01e9);
if(GA==-1) GA=G;
if(GA!=G) throw "GG";
sb[v[i][0]%G].pb(v[i][0]/G);
}
for(auto&u:sb)
sort(u.se.begin(),u.se.end());
}
int qry(int x)
{
if(GA==-1) return 0;
auto&w=sb[x%GA];
return upper_bound(w.begin(),w.end(),x/GA)-w.begin();
}
}A,B;
}
void count_routes(int N_, int M, int P, int R[][2], int Q, int G[])
{
using namespace Wrap;
n=N_,m=M,p=P,N=n*2;
for(int i=0;i<m;++i)
a[i]=R[i][0],b[i]=R[i][1],
e[a[i]].pb(i),
e[b[i]].pb(i);
for(int i=0;i<n;++i)
for(int j=0;j<2;++j)
{
int c=e[i].front();
if(j&&e[i].size()>1)
c=e[i][1];
int w=gb(c,i);
int d=(e[w].front()==c);
u[i*2+j]=w*2+d;
pre[w*2+d].pb(i*2+j);
}
A.init(P*2);
B.init(P*2+1);
for(int j=0;j<Q;++j)
answer(A.qry(G[j])+B.qry(G[j]));
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
63256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
63256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
60 ms |
63256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
