QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#490650 | #6559. A Tree and Two Edges | SmallAoPigBigPiPig# | TL | 1243ms | 1227392kb | C++17 | 2.3kb | 2024-07-25 16:00:24 | 2024-07-25 16:00:24 |
Judging History
answer
#include<bits/stdc++.h>
const int MAXN = 50011;
typedef std::pair<int,int> pii;
typedef std::bitset<MAXN> bits;
bits f[4][MAXN];
struct DSU
{
int fa[MAXN];
void init(int n)
{
for(int i=1;i<=n;++i)fa[i]=i;
}
int find(int x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
bool uni(int x,int y)
{
x=find(x),y=find(y);
if(x==y)return 0;
fa[x]=y;
return 1;
}
}dsu;
std::vector<int>g[MAXN];
pii e[2];
void dfs(int k,int u,int pre)
{
f[k][u]=f[k][pre];
f[k][u].set(u);
for(auto v:g[u])
if(v!=pre)
{
dfs(k,v,u);
}
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
dsu.init(n);
int c=0;
for(int i=1;i<=n+1;++i)
{
int u,v;
scanf("%d%d",&u,&v);
if(dsu.uni(u,v))g[u].emplace_back(v),g[v].emplace_back(u);
else e[c++]=pii(u,v);
}
for(int i=0;i<2;++i)
{
dfs(i<<1,e[i].first,0);
dfs(i<<1|1,e[i].second,0);
}
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
int ans=1;
for(int i=0;i<2;++i)
{
int a=e[i].first,b=e[i].second;
auto &fa=f[i<<1],&fb=f[i<<1|1];
if(!(fa[x]&fb[y]).any())++ans;
if(!(fb[x]&fa[y]).any())++ans;
}
// x->(a,b) -> (c,d) -> y
for(int i=0;i<2;++i)
{
int a=e[i].first,b=e[i].second;
int c=e[i^1].first,d=e[i^1].second;
auto &fa=f[i<<1],&fb=f[i<<1|1];
auto &fc=f[(!i)<<1],&fd=f[(!i)<<1|1];
//printf("consider (%d,%d) (%d,%d) (%d,,,)\n",a,b,c,d,fa[x].count());
if(!(fa[x]&fb[c]).any()&&!(fa[x]&fd[y]).any()&&!(fb[c]&fd[y]).any())++ans;
//printf("(%d,%d,%d)\n",(fb[x]&fa[c]).any(),(fb[x]&fd[y]).any(),(fa[c]&fd[y]).any());
if(!(fb[x]&fa[c]).any()&&!(fb[x]&fd[y]).any()&&!(fa[c]&fd[y]).any())++ans;
std::swap(fc,fd),std::swap(c,d);
if(!(fa[x]&fb[c]).any()&&!(fa[x]&fd[y]).any()&&!(fb[c]&fd[y]).any())++ans;
if(!(fb[x]&fa[c]).any()&&!(fb[x]&fd[y]).any()&&!(fa[c]&fd[y]).any())++ans;
std::swap(fc,fd);
}
printf("%d\n",ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1243ms
memory: 1227392kb
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: 820ms
memory: 1227200kb
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...