QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#706891 | #6559. A Tree and Two Edges | ucup-team902# | TL | 1ms | 8848kb | C++17 | 2.5kb | 2024-11-03 13:51:30 | 2024-11-03 13:51:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
#define bg begin
#define gc getchar
inline int read(){
char ch=gc();
int res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}
cs int N=50005;
vector<int> e[N];
int fa[N][20];
int in[N],q,n,out[N];
int dfn,dep[N];
void dfs(int u){
in[u]=++dfn;
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:e[u])if(v!=fa[u][0]){
fa[v][0]=u;
dep[v]=dep[u]+1;
dfs(v);
}
}
int Lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=19;~i;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
if(u==v)return u;
for(int i=19;~i;i--)if(fa[u][i]!=fa[v][i]){
u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
int stk[N],top,qu,qv,ans;
vector<int> ee[N];
vector<int>nd;
void add(int u,int v){
ee[u].pb(v);
ee[v].pb(u);
nd.pb(u);
nd.pb(v);
}
int vs[N];
void ddfs(int u){
if(u==qv){
ans++;return;
}
vs[u]=1;
for(int v:ee[u])if(!vs[v]){
ddfs(v);
}
vs[u]=0;
}
int ff[N];
int find(int x){
return ff[x]==x?x:ff[x]=find(ff[x]);
}
int main(){
#ifdef Stargazer
freopen("1.in","r",stdin);
#endif
n=read(),q=read();
pii x(0,0),y(0,0);
for(int i=1;i<=n;i++)ff[i]=i;
for(int i=1;i<=n+1;i++){
int u=read(),v=read();
int f1=find(u),f2=find(v);
if(f1!=f2)
e[u].pb(v),e[v].pb(u),ff[f1]=f2;
else{
if(!x.fi)x.fi=u,x.se=v;
else if(x.fi&&!y.fi)y.fi=u,y.se=v;
}
}
//cout<<x.fi<<" "<<x.se<<" "<<y.fi<<" "<<y.se<<'\n';
dep[1]=1;
dfs(1);
while(q--){
qu=read(),qv=read();
vector<int> c;
c.pb(qu),c.pb(qv);
c.pb(x.fi),c.pb(x.se),c.pb(y.fi),c.pb(y.se);
sort(c.begin(),c.end(),[](int i,int j){return in[i]<in[j];});
top=0;
for(int i=0;i<c.size();i++){
int x=c[i];
if(top){
int lca=Lca(x,stk[top]);
if(in[lca]<in[stk[top]]){
while(top>1&&in[lca]<in[stk[top-1]])add(stk[top-1],stk[top]),top--;
add(lca,stk[top--]);
if(stk[top]!=lca)stk[++top]=lca;
}
}
stk[++top]=x;
}
while(top>1)add(stk[top-1],stk[top]),top--;
add(x.fi,x.se);
add(y.fi,y.se);
ans=0;
ddfs(qu);
cout<<ans<<'\n';
for(int x:nd)ee[x].clear();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 8652kb
input:
4 6 1 2 1 3 1 4 2 3 2 4 1 2 1 3 1 4 2 3 2 4 3 4
output:
3 3 3 3 3 4
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 8848kb
input:
6 4 1 2 1 3 1 6 2 3 3 4 3 5 4 5 1 2 1 3 1 4 1 6
output:
2 2 4 1
result:
ok 4 lines
Test #3:
score: -100
Time Limit Exceeded
input:
50000 50000 11561 23122 14261 28523 24407 48814 17947 35894 14803 29607 19557 39115 12415 24830 9583 19167 18397 36794 439 878 18040 36080 17150 34300 7922 15845 18938 37877 18625 37250 6459 12919 9818 19636 3579 7158 21323 42646 23882 47764 13603 27207 8353 16707 15907 31814 20935 41871 11686 23372...
output:
4 3 3 4 4 3 1 3 4 1 3 4 3 4 3 3 1 3 3 3 4 4 4 3 3 3 4 3 3 3 1 3 3 3 3 4 4 4 4 3 4 3 3 3 4 3 4 4 4 4 3 4 4 4 4 3 3 3 4 4 4 4 4 4 3 4 3 4 1 4 1 1 4 3 3 4 3 3 1 4 3 3 4 4 3 3 4 4 4 3 4 3 4 4 4 4 4 3 4 3 3 3 1 3 4 4 3 4 3 4 3 3 4 1 4 3 3 3 4 4 4 4 3 3 3 3 3 4 4 4 4 3 3 4 3 4 4 3 3 4 4 4 1 3 3 3 3 4 4 3 ...