QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291346 | #4896. Alice、Bob 与 DFS | Kevin5307 | 0 | 0ms | 0kb | C++20 | 3.1kb | 2023-12-26 12:43:05 | 2023-12-26 12:43:06 |
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int c[400400];
vector<int> G[400400];
int n;
ll g0[400400],g1[400400];
namespace bit
{
int bit[400400];
vector<pii> memo;
void update(int p,int v,bool ign=0)
{
if(!ign)
memo.pb(p,v);
p++;
while(p<400400)
{
bit[p]+=v;
p+=(p&(-p));
}
}
int query(int p)
{
p++;
int ans=0;
while(p)
{
ans+=bit[p];
p-=(p&(-p));
}
return ans;
}
void clear()
{
for(auto pr:memo)
update(pr.first,-pr.second,1);
memo.clear();
}
}
void get()
{
for(int i=n;i>=1;i--)
if(c[i])
{
rev(G[i]);
{
bit::update(0,1);
for(auto j:G[i]) if(c[j])
{
int cur=g0[j];
int l=0,r=400001;
while(l<r)
{
int mid=(l+r)/2;
if((mid+1)-bit::query(mid)>=cur)
r=mid;
else
l=mid+1;
}
bit::update(l,1);
}
else
{
int cur=g0[j];
if(bit::query(cur)==bit::query(cur-1))
bit::update(cur,1);
}
int l=0,r=400001;
while(l<r)
{
int mid=(l+r)/2;
if((mid+1)-bit::query(mid))
r=mid;
else
l=mid+1;
}
g0[i]=l;
bit::clear();
}
{
for(auto j:G[i]) if(c[j])
{
int cur=(bit::query(0)?g0[j]:g1[j]+1);
int l=0,r=400001;
while(l<r)
{
int mid=(l+r)/2;
if((mid+1)-bit::query(mid)>=cur)
r=mid;
else
l=mid+1;
}
bit::update(l,1);
}
else
{
int cur=(bit::query(0)?g0[j]:g1[j]);
if(bit::query(cur)==bit::query(cur-1))
bit::update(cur,1);
}
int l=0,r=400001;
while(l<r)
{
int mid=(l+r)/2;
if((mid+1)-bit::query(mid))
r=mid;
else
l=mid+1;
}
g1[i]=l;
bit::clear();
}
}
else
{
int cur0=0,cur1=1;
rev(G[i]);
for(auto j:G[i])
{
cur0=(cur0?g1[j]:g0[j]);
cur1=(cur1?g1[j]:g0[j]);
}
g0[i]=cur0^1;
g1[i]=cur1^1;
}
}
int main()
{
freopen("Genshin_lmpact.in","r",stdin);
freopen("Genshin_lmpact.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
{
int m;
cin>>m;
if(!m) c[i]=1;
while(m--)
{
int x;
cin>>x;
G[i].pb(x);
}
}
get();
// for(int i=1;i<=n;i++)
// cerr<<g0[i]<<" "<<g1[i]<<endl;
int k;
cin>>k;
int ans=0;
while(k--)
{
int x;
cin>>x;
ans^=g0[x];
}
if(ans)
cout<<"Alice";
else
cout<<"Bob";
return 0;
}
詳細信息
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #18:
score: 0
Dangerous Syscalls
input:
7 0 0 1 1 0 1 1 1 2 2 3 4 0 2 5 6 0 1 7 0 1 1
output:
result:
Subtask #3:
score: 0
Dangerous Syscalls
Test #55:
score: 0
Dangerous Syscalls
input:
7 0 0 1 1 0 1 1 1 2 2 3 4 0 2 5 6 0 1 7 0 1 1
output:
result:
Subtask #4:
score: 0
Dangerous Syscalls
Test #103:
score: 0
Dangerous Syscalls
input:
10 1 1 1 1 1 1 1 1 1 1 1 2 4 3 5 7 8 1 4 0 1 6 0 0 1 9 1 10 0 1 1
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%