This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define pb push_back
#define sll set<ll>
const int N=5e3+10;
vll ma[N];
bool charge[N],alive[N],vis[N];
sll rem;
ll n,owner[N],m,deg[N],deg_[N];
sll attr(sll& a,ll player)
{
ll sz=a.size();
for(auto&i:rem)
{
vis[i]=0;
deg_[i]=deg[i];
}
// cout<<"Computing attractor of: ";
queue<int> q;
for(auto&i:a)
{
// cout<<i<<' ';
if(alive[i])
{
q.push(i);
vis[i]=1;
}
}
// cout<<endl;
sll ans;
// cout<<"reach: ";
while(q.size())
{
int f=q.front();
q.pop();
ans.insert(f);
// cout<<f<<' ';
for(ll&y:ma[f])
{
if(!alive[y])continue;
deg_[y]--;
if(owner[y]==player)
{
// y have edge to the set a and is own by palyer so he will take the edge
if(!vis[y])
{
vis[y]=1;
q.push(y);
}
}
else // Owned by other player
{
if(deg_[y]==0 and vis[y]==0)
{
vis[y]=1;
q.push(y);
}
}
}
}
// cout<<endl;
return ans;
}
sll attrcomp(sll& a,ll player)
{
// We never want to reach any vertex in a
// Reach(a) == compliement( Safety( compliment( a ) ) )
// Reach( compliment ( a ) ) == compliement( Safety( a ) )
// compliment( Reach( compliment ( a ) ) ) == Safety( a )
sll cp;
for(auto&i:a)
cp.insert(i);
// if(a.find(i)==a.end())
cp=attr(cp,player);
sll ans;
for(auto&i:rem)
if(cp.find(i)==cp.end())
ans.insert(i);
return ans;
}
sll Buchi(sll& a)
{
ll sz=a.size();
while(true)
{
auto cur=attrcomp(a,1);
if(cur.size()==0)break;
// cout<<"Step\n";
// cout<<"For a: ";
// for(auto i:a)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// cout<<"Got cur: ";
// for(auto i:cur)
// {
// cout<<i<<' ';
// }
// cout<<endl;
cur=attr(cur,2);
// cout<<"Got cur: ";
// for(auto i:cur)
// {
// cout<<i<<' ';
// }
// cout<<endl;
for(auto&i:cur){
auto it=a.find(i);
if(it!=end(a))
a.erase(it);
auto it1=rem.find(i);
if(it1!=end(rem))
{
for(auto jp:ma[i])
deg[jp]--;
alive[i]=0;
deg[i]=0;
ma[i].clear();
rem.erase(it1);
}
}
}
return a;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v)
{
n=a.size();
sll vertexs;
for(int i=1;i<=n;i++)
{
rem.insert(i);
alive[i]=1;
if(a[i-1]==1)
{
owner[i]=1;
}
else
{
owner[i]=2;
}
if(r[i-1])
{
vertexs.insert(i);
charge[i]=1;
}
else
{
charge[i]=0;
}
}
m=u.size();
for(int j=0;j<m;j++)
{
u[j]++;
v[j]++;
ma[v[j]].pb(u[j]); // Directed edges
deg[u[j]]++;
// ma[v[j]].pb(u[j]);
}
sll answer=Buchi(vertexs);
vector<int> ap(n);
for(int i=1;i<=n;i++)
ap[i-1]=alive[i];
return ap;
}
Compilation message (stderr)
train.cpp: In function 'std::set<long long int> attr(std::set<long long int>&, long long int)':
train.cpp:16:8: warning: unused variable 'sz' [-Wunused-variable]
16 | ll sz=a.size();
| ^~
train.cpp: In function 'std::set<long long int> Buchi(std::set<long long int>&)':
train.cpp:87:8: warning: unused variable 'sz' [-Wunused-variable]
87 | ll sz=a.size();
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |