| 记录编号 |
189065 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[国家集训队 2011] 公交路线 |
最终得分 |
100 |
| 用户昵称 |
 四季木哥 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
7.069 s |
| 提交时间 |
2015-09-25 22:05:40 |
内存使用 |
50.81 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define N 200550
#define INF 0x3f3f3f3f
using namespace std;
int pre[N][22], C[N], dfn[N], end[N], fa[N][22], dep[N], cnt[N], vis[N];
int S[N], T[N], cur, answer[N], num[N];
int n, t, m, _dfn;
vector<int> G[N];
vector<int> p[N];
vector<int> quest[N*2];
void get(int &x){
char c = getchar(); x = 0;
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}
inline int lowbit(int x){
return x&(-x);
}
inline int sum(int x){
int ret=0;
while(x>0) {
ret+=C[x]; x-=lowbit(x);
}
return ret;
}
inline void add(int x){
while(x<=end[1]){
C[x]++; x+=lowbit(x);
}
}
void DFS(int x, int depth){
if(vis[x]) return;
vis[x]=1;
int siz=G[x].size();
dfn[x]=++_dfn;
dep[x]=depth;
if(!siz){
end[x]=dfn[x];
return;
}
int v;
for(int i=0;i<siz;i++){
v=G[x][i];
if(!vis[v]) fa[v][0]=x;
DFS(v,depth+1);
}
end[x]=++_dfn;
}
void get_pre(int x){
if(!vis[x]) return;
vis[x]=0;
int siz=G[x].size();
for(int i=0;i<siz;i++) get_pre(G[x][i]);
if(dfn[pre[x][0]]<dfn[pre[fa[x][0]][0]])
pre[fa[x][0]][0]=pre[x][0];
}
inline void find_fa(void){
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
inline void move_up(void){
get_pre(1);
for(int i=1;i<=n;i++) if(!pre[i][0]) pre[i][0]=i;
for(int j=1;j<=17;j++){
for(int i=1;i<=n;i++){
pre[i][j]=pre[pre[i][j-1]][j-1];
}
}
}
inline int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int i;
for(i=0;dep[x]-(1<<i)>=dep[y];i++)
x=fa[x][i];
if(dep[x]>=dep[y]){
for(int j=i-1;j>=0;j--)
if(dep[fa[x][j]]>=dep[y])
x=fa[x][j];
}
for(i=0;fa[x][i]!=fa[y][i];i++){
x=fa[x][i];
y=fa[y][i];
}
for(int j=i-1;j>=0;j--){
if(fa[x][j]!=fa[y][j]){
x=fa[x][j];
y=fa[y][j];
}
}
return fa[x][0];
}
inline void Add_Point(int x, int y){
p[dfn[x]].push_back(dfn[y]);
p[dfn[y]].push_back(dfn[x]);
}
inline void Deal_Point(void){
for(int i=1;i<=cur;i++){
quest[dfn[S[i]]-1].push_back(-i);
quest[end[S[i]]].push_back(i);
}
for(int i=0;i<=_dfn;i++){
int siz=p[i].size();
for(int j=0;j<siz;j++) add(p[i][j]);
siz=quest[i].size();
for(int j=0;j<siz;j++){
int k=abs(quest[i][j]);
int now=sum(end[T[k]])-sum(dfn[T[k]]-1);
if(quest[i][j]<0) cnt[k]-=now;
else cnt[k]+=now;
}
}
for(int i=1;i<=cur;i++)
if(cnt[i]<=0) answer[num[i]]++;
}
inline int Ask(int x,int y,int k){
int ans=0;
if(dfn[x]<dfn[y]) swap(x,y);
if(dfn[x]<=end[y]){
int i;
for(i=0;dfn[pre[x][i]]>dfn[y];i++){
if(x==pre[x][i]) return -1;
x=pre[x][i];
ans+=(1<<i);
}
for(int j=i-1;j>=0;j--){
if(x==pre[x][i]) return -1;
if(dfn[pre[x][j]]>dfn[y]){
x=pre[x][j];
ans+=(1<<j);
}
}
}else{
int i;
int lca=LCA(x,y);
for(i=0;dfn[pre[x][i]]>dfn[lca];i++){
if(x==pre[x][i]) return -1;
x=pre[x][i];
ans+=(1<<i);
}
for(int j=i-1;j>=0;j--){
if(x==pre[x][0]) return -1;
if(dfn[pre[x][j]]>dfn[lca]){
x=pre[x][j];
ans+=(1<<j);
}
}
for(i=0;dfn[pre[y][i]]>dfn[lca];i++){
if(y==pre[y][i]) return -1;
y=pre[y][i];
ans+=(1<<i);
}
for(int j=i-1;j>=0;j--){
if(y==pre[y][i]) return -1;
if(dfn[pre[y][j]]>dfn[lca]){
y=pre[y][j];
ans+=(1<<j);
}
}
S[++cur]=x;
T[cur]=y;
num[cur]=k;
}
return ans;
}
inline void work(void){
get(n);get(t);get(m);
int x, y;
for(int i=1;i<n;i++){
get(x); get(y);
G[x].push_back(y);
G[y].push_back(x);
}
dfn[0]=INF;end[0]=-INF;fa[1][0]=1;
DFS(1,1);
find_fa();
for(int i=1;i<=t;i++){
get(x); get(y);
if(dfn[x]<dfn[y]) swap(x,y);
if(end[x]<end[y]) {
if(dfn[pre[x][0]]>dfn[y])
pre[x][0]=y;
}
else {
int lca=LCA(x,y);
if(dfn[pre[x][0]]>dfn[lca]) pre[x][0]=lca;
if(dfn[pre[y][0]]>dfn[lca]) pre[y][0]=lca;
Add_Point(x,y);
}
}
move_up();
}
int main(void){
freopen("nt2011_bus.in","r",stdin);
freopen("nt2011_bus.out","w",stdout);
work();
int x, y;
for(int i=1;i<=m;i++){
get(x); get(y);
answer[i]=Ask(x,y,i);
}
Deal_Point();
for(int i=1;i<=m;i++) printf("%d\n",answer[i]);
return 0;
}