[2017 호남 합숙 7-8] 암목허수+최단로
16782 단어 허수
코드:
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=300010;
const int maxm=201000;
const int mod=3999997;
const ll inf=1e12;
int n,m,q,dl[maxm<<2],deep[maxn],dfn[maxn],f[maxn][20],ch[maxn],st[maxn],tim,num=0;
bool visit[maxm<<2];
ll dist[maxm<<2];
struct dor
{
int p1,p2,u1,u2;
}d[maxm],c;
struct edge
{
int t,w;
edge *next;
}*con[maxm<<2],*dor[maxm],*imp[maxm<<1],*tr[maxn],*hash[4000010];
inline int ds(int x,int y) {return deep[x]-deep[y];}
void instr(int x,int y)
{
edge *p;
p=new edge;
p->t=y;
p->next=tr[x];
tr[x]=p;
}
void insimp(int x,int y)
{
edge *p;
p=new edge;
p->t=y;
p->next=imp[x];
imp[x]=p;
}
int insh(ll x)
{
edge *p;
p=new edge;
p->t=x/mod;
p->w=(++num);
p->next=hash[x%mod];
hash[x%mod]=p;
return num;
}
void inscon(int x,int y,int w)
{
if(x==y) return ;
edge *p;
p=new edge;
p->t=y;p->w=w;
p->next=con[x];
con[x]=p;
}
int geth(ll x)
{
for(edge *p=hash[x%mod];p!=NULL;p=p->next)
if(p->t==x/mod) return p->w;
return -123;
}
int lca(int x,int y)
{
if(deep[x]>deep[y]) swap(x,y);
for(int k=19;k>=0&&deep[x]y];k--)
if(deep[f[y][k]]>=deep[x]) y=f[y][k];
if(x==y) return x;
for(int k=19;k>=0;k--)
if(f[x][k]!=f[y][k]){x=f[x][k]; y=f[y][k];}
return f[x][0];
}
void dfs1(int v)
{
deep[v]=deep[f[v][0]]+1;
dfn[v]=(++tim);
for(edge *p=tr[v];p!=NULL;p=p->next)
if(p->t!=f[v][0])
{
f[p->t][0]=v;
dfs1(p->t);
}
}
bool cmp(int a,int b)
{
return dfn[a]int v)
{
int top=0;
ll ad=(ll)(v-1)*n;
for(edge *p=imp[v];p!=NULL;p=p->next)
{
ch[++top]=p->t;
insh(ad+p->t);
}
if(top==0) return ;
sort(ch+1,ch+top+1,cmp);
int tmp=0;
for(int i=1;i<=top;i++)
if(ch[i]!=ch[tmp]) ch[++tmp]=ch[i];
top=tmp;
int stp=1;
st[1]=ch[1];
for(int i=2;i<=top;i++)
{
while(1)
{
int tlca=lca(ch[i],st[stp]),last=st[stp];
if(st[stp]==tlca) {st[++stp]=ch[i];break;}
if(ds(st[stp-1],tlca)>=0) stp--;
else {st[stp]=tlca;insh(ad+tlca);}
inscon(geth(ad+last),geth(ad+st[stp]),ds(last,st[stp]));
inscon(geth(ad+st[stp]),geth(ad+last),ds(last,st[stp]));
}
}
for(int i=stp-1;i>0;i--)
{
inscon(geth(ad+st[i+1]),geth(ad+st[i]),ds(st[i+1],st[i]));
inscon(geth(ad+st[i]),geth(ad+st[i+1]),ds(st[i+1],st[i]));
}
}
inline int nxt(int x)
{
return x+1-((x+1==800000)?800000:0);
}
ll spfa(int s,int t)
{
int head=1,tail=1;
memset(dist,0x3f,sizeof(dist));
memset(visit,0,sizeof(visit));
dl[1]=s;
visit[s]=1;
dist[s]=0;
while(head!=tail+1)
{
int v=dl[head];
for(edge *p=con[v];p!=NULL;p=p->next)
if(dist[p->t]>dist[v]+p->w)
{
dist[p->t]=dist[v]+p->w;
if(!visit[p->t])
{
dl[(tail=nxt(tail))]=p->t;
visit[p->t]=1;
}
}
visit[dl[(head=nxt(head))]]=0;
}
return dist[t];
}
int main()
{
freopen("m.in","r",stdin);
freopen("m.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
instr(x,y);
instr(y,x);
}
f[1][0]=0;
dfs1(1);
for(int k=1;(1<for(int i=1;i<=n;i++)
if(f[i][k-1]!=0) f[i][k]=f[f[i][k-1]][k-1];
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&d[i].p1,&d[i].u1,&d[i].p2,&d[i].u2);
insimp(d[i].u1,d[i].p1);
insimp(d[i].u2,d[i].p2);
}
for(int i=1;i<=200000;i++)
build(i);
for(int i=1;i<=m;i++)
{
int o1=geth((ll)(d[i].u1-1)*n+d[i].p1),o2=geth((ll)(d[i].u2-1)*n+d[i].p2);
inscon(o1,o2,1);
inscon(o2,o1,1);
}
int lst=num;
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d",&c.p1,&c.u1,&c.p2,&c.u2);
ll ad1=(ll)(c.u1-1)*n,ad2=(ll)(c.u2-1)*n;
int tmp;
for(edge *p=imp[c.u1];p!=NULL;p=p->next)
{
tmp=lca(c.p1,p->t);
inscon(lst+1,geth(ad1+p->t),ds(c.p1,tmp)+ds(p->t,tmp));
}
for(edge *p=imp[c.u2];p!=NULL;p=p->next)
{
tmp=lca(c.p2,p->t);
inscon(geth(ad2+p->t),lst+2,ds(c.p2,tmp)+ds(p->t,tmp));
}
if(c.u1==c.u2)
{
tmp=lca(c.p1,c.p2);
inscon(lst+1,lst+2,ds(c.p1,tmp)+ds(c.p2,tmp));
}
ll ans=spfa(lst+1,lst+2);
lst+=2;
if(ans==0x3f3f3f3f3f3f3f3f) puts("impossible");
else printf("%lld
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CCPC-Wannafly Winter Camp Day5(Div1, onsite)(Nested Tree-빈 트리)각 복제본에 대해 모든 포인트 쌍을 집계하는 lca가 해당 복제본의 경로에서 응답에 기여하는 서브트리의 복사본 a n s + = d e p s u m a ∗ t o t v + n ∗ d e p s v + n ∗ t ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.