URL 已经复制到剪切板

查看 gist

查看一个gist的详细信息

简介

名称

7d6eb5a0-20ab-409d-b0c6-0918451e5451

创建者

rsl

创建时间

2017-08-10 00:34

最后修改

2017-08-10 00:34

代码
#include <iostream> #include <cstdio> #include <algorithm> #include <math.h> #include <string.h> #include <map> #define LL long long using namespace std; const int M = 1000000007; const int N = 80005; int n,m,a,b,c; struct ls { int nx,u,v,w; }s[N]; int head[N],first[N],ver[N],R[N]; int dis[N],st[N][20],vis[N],pos=0,tot=0; int min(int a,int b) { return a<b?a:b; } void add(int x,int y,int c) { s[pos].u=x; s[pos].v=y; s[pos].w=c; s[pos].nx=head[x]; head[x]=pos++; } void DFS(int x,int deep) { vis[x]=1; first[x]=tot; ver[tot]=x; R[tot]=deep; tot++; for (int i=head[x];i!=-1;i=s[i].nx) { int e=s[i].v; if (vis[e]==0) { dis[e]=dis[x]+s[i].w; DFS(e,deep+1); ver[tot]=x; R[tot]=deep; tot++; } } } void gest(int n) { for (int j=0;(1<<j)<n;j++) for (int i=1;i+(1<<j)-1<n;i++) { if (j==0) st[i][j]=i; else { int a=st[i][j-1]; int b=st[i+(1<<(j-1))][j-1]; st[i][j]=R[a]<R[b]?a:b; } } } int query(int l,int r) { int k=0; while ((1<<(k+1))<=r-l+1) k++; int a=st[l][k]; int b=st[r-(1<<k)+1][k]; return R[a]<R[b]?a:b; } int LCA(int a,int b) { a=first[a]; b=first[b]; if (a>b) swap(a,b); int v=query(a,b); return ver[v]; } map <string,int> mp; char s1[N],t[N]; void ini() { pos=0; tot=1; memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); memset(st,0,sizeof(st)); mp.clear(); } string tp; int main() { int T; // scanf("%d",&T); int cas=1; while (~scanf("%s %d",s1,&n)) { if (cas!=1) printf("\n"); ini(); int pos=1; tp=s1; mp[tp]=pos++; for (int i=0;i<n;i++) { scanf("%s%s",s1,t); tp=s1; if (mp[tp]==0) mp[tp]=pos++; int a = mp[tp]; tp=t; if (mp[tp]==0) mp[tp]=pos++; int b = mp[tp]; add(b, a,1); } DFS(1,1); gest(mp.size()*2-1); printf("Project %d\n",cas++); scanf("%d",&m); for (int i=0;i<m;i++) { scanf("%s%s",s1,t); tp=s1; int a = mp[tp]; tp=t; int b = mp[tp]; int temp=LCA(a,b); // cout<<"bug "<<a<<" "<<b<<" "<<temp<<endl; if (temp==b) printf("Yes\n"); else printf("No\n"); } } return 0; } /* Object 3 Integer Object List Object LinkedList List 3 Integer Object LinkedList List Integer List */
分享