Submission #1065783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065783		Faisal_Saqib	Toy Train (IOI17_train)	C++17	26 / 100	470 ms	2936 KiB

train

#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(a.size()>0)
	{
		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:5: 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:5: warning: unused variable 'sz' [-Wunused-variable]
   87 |  ll sz=a.size();
      |     ^~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51