主要利用了宏和stderr...
#define enable_debug
#ifdef enable_debug
FILL some macros/functions here
#else
/// set some debug functions to NULL
#endif
1. 输出到stderr
#define debug(...) { \
fprintf(stderr,__VA_ARGS__); \
fflush(stderr); \
} \
2. 若debug则插入一段代码
#define ProgDBG(...) { __VA_ARGS__; }
example.
#include "cstdio"
#include "vector"
#include "cstring"
#include "cstdlib"
#include "algorithm"
#define pb push_back
#define frp(x,y,z) freopen(#x"."#z,#y,std##z);
using namespace std;
const int
maxn = 50010,
maxm = 100010;
struct node;
struct ed{
node*f,*t;
ed*r;
} AlEd[maxn<<2],*p=AlEd;
struct node{
vector<ed*> To,Eto;
int id,nid,color;
int dist1,dist2;
} nd [maxn];
inline void ade(int f,int t){
*p=(ed){nd+f,nd+t,p+1};
nd[f].Eto.pb(p);
nd[f].To.pb(p++);
*p=(ed){nd+t,nd+f,p-1};
nd[t].Eto.pb(p);
nd[t].To.pb(p++);
}
struct qry{ int f,t,id; } qrs[maxm];
int nowColor,ans[maxm];
//#define idbg
#ifdef idbg
#define debug(...) {fprintf(stderr,__VA_ARGS__);fflush(stderr);}
// #define assert(...)
inline void tensenx(int&p,int b){
if(b<p) p=b;
}
#define xassert(x,...) if(!(x)){ \
debug(__VA_ARGS__);exit(3); \
}
#define tensen(a,...) { \
int t=__VA_ARGS__; \
xassert(t >= 0,"Tensened with: %d, code:\n" #__VA_ARGS__,t); \
tensenx(a,t); \
}
#define ProgDBG(...) { __VA_ARGS__; }
#else
#define debug(...)
inline void tensen(int&p,int b){
if(b<p) p=b;
}
#define ProgDBG(...)
#endif
typedef vector<node*> vn;
typedef vector<qry*> vq;
/// generate bfs functions
#define bfsx(x) inline void bfs##x(node*from){ \
ProgDBG( debug("BFS"#x"\n"); ) \
static node*queue[maxn]; \
int ql=0,qr=1,col=from->color; \
queue[0]=from; \
from->dist##x=0; \
while(ql-qr){ \
node*v=queue[ql++]; \
ProgDBG( \
debug("Vis %d\n",v->id); \
) \
for(int i=0,_=v->Eto.size();i<_;++i){ ed*p=v->Eto[i]; \
if(p->t->color==col && !(~p->t->dist##x)){ \
p->t->dist##x=v->dist##x+1; \
queue[qr++]=p->t; \
}else{ \
ProgDBG( \
if(p->t->color!=col){ \
debug("%d color not match\n",p->t->id); \
}else{ \
debug("%d dist"#x"(%d) mismatch\n",p->t->id,p->t->dist##x); \
} \
) \
} \
} \
} \
}
/// bfs1 & bfs2
bfsx(1);
bfsx(2);
void div(vn nodeList,vq qryList){
ProgDBG(
debug("Div Nodes: ");
for(int i=0,_=nodeList.size();i<_;++i){
debug("%d ",nodeList[i]->id);
}
debug("\n");
);
if(nodeList.size()<=3){
for(int i=0,_=qryList.size();i<_;++i){
tensen(ans[qryList[i]->id],qryList[i]->f!=qryList[i]->t);
}
}else{
int color=nowColor++;
for(int i=0,_=nodeList.size();i<_;++i){
nodeList[i]->color=color;
nodeList[i]->nid =i;
nodeList[i]->dist1=-1;
nodeList[i]->dist2=-1;
}
/// Find edge to cut.
int len=nodeList.size();
int maxlen=len;
ed*cur=NULL;
for(int i=0,_=nodeList.size();i<_;++i){
for(int j=0,_=nodeList[i]->Eto.size();j<_;++j){ ed*p=nodeList[i]->Eto[j];
if(p->t->color==color){
ProgDBG(
debug("Has Edge: %d -> %d\n",p->f->id,p->t->id);
)
int fx=p->f->nid,
tx=p->t->nid;
if(fx>tx) std::swap(fx,tx);
int na=fx+len-tx+1;
int nb=tx-fx+1;
na=na>nb?na:nb;
if(na<maxlen) maxlen=na, cur=p;
}
}
}
/// Calculate answer through this edge and divide the queries
bfs1(cur->f);
bfs2(cur->t);
int ef=cur->f->nid;
int et=cur->t->nid;
ProgDBG(
debug("Cut edge: (NID) %d %d\n",ef,et);
debug(" (ID) %d %d\n",cur->f->id,cur->t->id);
)
if(ef>et) std::swap(ef,et);
vq qryA,qryB;
for(int i=0,_=qryList.size();i<_;++i){
qry*p=qryList[i];
tensen(ans[p->id],nd[p->f].dist1+nd[p->t].dist1);
tensen(ans[p->id],nd[p->f].dist1+nd[p->t].dist2+1);
tensen(ans[p->id],nd[p->f].dist2+nd[p->t].dist1+1);
debug("%d %d %d %d\n",p->f,nd[p->f].dist2,p->t,nd[p->t].dist2);
tensen(ans[p->id],nd[p->f].dist2+nd[p->t].dist2);
int qf=nd[p->f].nid;
int qt=nd[p->t].nid;
if(qf>qt) std::swap(qf,qt);
if(qf==ef && qt==et) continue;
if(qf<=ef){
if(qt>=et || qt<=ef) qryA.pb(p);
}else
if(qf>=et) qryA.pb(p);
if(qf>=ef && qf<=et){
if(qt>=ef && qt<=et) qryB.pb(p);
}
}
/// divide nodes
vn ndA,ndB;
for(int i=0,_=nodeList.size();i<_;++i){
if(i<=ef) ndA.pb(nodeList[i]);
if(i>=et) ndA.pb(nodeList[i]);
if(i>=ef && i<=et) ndB.pb(nodeList[i]);
}
vector<ed*> pat=nodeList[ef]->Eto;
vector<ed*> pbt=nodeList[et]->Eto;
vector<ed*> qat, qbt, xat, xbt;
for(int i=0,_=pat.size();i<_;++i){
if(pat[i]->t->nid<=ef) qat.pb(pat[i]);
if(pat[i]->t->nid>=et) qat.pb(pat[i]);
if(pat[i]->t->nid>=ef && pat[i]->t->nid<=et) qbt.pb(pat[i]);
}
for(int i=0,_=pbt.size();i<_;++i){
if(pbt[i]->t->nid<=ef) xat.pb(pbt[i]);
if(pbt[i]->t->nid>=et) xat.pb(pbt[i]);
if(pbt[i]->t->nid>=ef && pbt[i]->t->nid<=et) xbt.pb(pbt[i]);
}
nodeList[ef]->Eto=qat; nodeList[et]->Eto=xat;
div(ndA,qryA);
nodeList[ef]->Eto=qbt; nodeList[et]->Eto=xbt;
div(ndB,qryB);
}
}
int main(){
frp(B,r,in);
frp(B,w,out);
int n; scanf("%d",&n);
for(int i=1;i<=n;++i) ade(i,i%n+1),nd[i].id=i;
for(int i=3;i< n;++i){
int a,b; scanf("%d%d",&a,&b); ade(a,b);
}
int q; scanf("%d",&q);
for(int i=1;i<=q;++i){ scanf("%d%d",&qrs[i].f,&qrs[i].t); qrs[i].id=i; }
vn A; vq B;
for(int i=1;i<=n;++i) A.pb(nd+i);
for(int i=1;i<=q;++i) B.pb(qrs+i);
memset(ans,0x3f,sizeof(ans));
div(A,B);
for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
return 0;
}