F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 3757 >> 莫名RE
jyz1232012 @ 2018-02-10 19:09:49
[ Quote ] [ Edit ] [ Delete ] 1#
//求助:本机测试AC,用NOI LINUX测试也是AC,对拍能通过,但是提交之后就RE
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<set>
#include<complex>
#include<map>
using namespace std;
inline int ri()
{
register int x=0;
bool f=0;
register char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
if(f) return -x;
else return x;
}
void wi(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) wi(x/10);
putchar(x%10+'0');
}
const int N=50005;
int head[N],nxt[N<<1],to[N<<1];
int col[N],be[N],stk[N],ans[N<<1],tot=1,sum,B;
int fa[N],sz[N],son[N],top[N],deep[N],cnt[N],vis[N];
struct qry
{
int u,v,a,b,id;
char operator < (const qry x)const
{
return be[x.u]==be[u]?be[v]<be[x.v]:be[u]<be[x.u];
}
}q[N<<1];
inline void ade(int x,int y)
{
nxt[++nxt[0]]=head[x];
head[x]=nxt[0];
to[nxt[0]]=y;
}
void dfs(int x)
{
deep[x]=deep[fa[x]]+1;
sz[x]=1;
int now,bot=stk[0];
for(now=head[x];now;now=nxt[now])
{
if(to[now]==fa[x]) continue;
fa[to[now]]=x;
dfs(to[now]);
sz[x]+=sz[to[now]];
if(sz[son[x]]<sz[to[now]]) son[x]=to[now];
if(stk[0]-bot>=B)
for(tot++;stk[0]!=bot;be[stk[stk[0]--]]=tot);
}
stk[++stk[0]]=x;
}
void dfs2(int x,int tp)
{
top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(int now=head[x];now;now=nxt[now])
{
if(to[now]==fa[x]||to[now]==son[x]) continue;
dfs2(to[now],to[now]);
}
}
inline int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]>deep[top[y]]) swap(x,y);
y=fa[top[y]];
}
if(deep[x]>deep[y]) swap(x,y);
return x;
}
inline void point(int x)
{
if(vis[x])
{
cnt[col[x]]--;
if(cnt[col[x]]==0) sum--;
}
else
{
cnt[col[x]]++;
if(cnt[col[x]]==1) sum++;
}
vis[x]^=1;
}
inline void go(int u,int v)
{
while(u!=v)
{
if(deep[u]>deep[v]) swap(u,v);
point(v);v=fa[v];
}
}
int main()
{
register int n=ri(),m=ri(),i,x,y,a;
B=sqrt(n);
for(i=1;i<=n;i++) col[i]=ri();
for(i=1;i<=n;i++)
{
x=ri(),y=ri();
ade(x,y);
ade(y,x);
}
for(i=1;i<=m;i++)
q[i].u=ri(),q[i].v=ri(),q[i].a=ri(),q[i].b=ri(),q[i].id=i;
dfs(1);
dfs2(1,1);
while(stk[0]) be[stk[stk[0]--]]=tot;
sort(q+1,q+1+m);
for(i=x=y=1;i<=m;i++)
{
go(x,q[i].u),x=q[i].u;
go(y,q[i].v),y=q[i].v;
a=lca(x,y);
point(a);
ans[q[i].id]=sum-(q[i].a!=q[i].b&&cnt[q[i].a]&&cnt[q[i].b]);
point(a);
}
for(i=1;i<=m;i++) wi(ans[i]),putchar('\n');
return 0;
}
EdwardFrog @ 2018-02-10 20:26:06
[ Quote ] [ Edit ] [ Delete ] 2#
原谅我笑出声了...
你看一下提交记录吧...
[Top] [Previous Page] [Next Page]

HOME Back