oj.uz

Submission #1065783

# Submission time Handle Problem Language Result Execution time Memory
1065783 2024-08-19T11:43:24 Z Faisal_Saqib Toy Train (IOI17_train) C++17
26 / 100
 470 ms 2936 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2140 KB Output is correct
2 Correct 10 ms 2140 KB Output is correct
3 Correct 9 ms 2140 KB Output is correct
4 Correct 9 ms 2140 KB Output is correct
5 Correct 8 ms 1976 KB Output is correct
6 Correct 8 ms 1884 KB Output is correct
7 Correct 5 ms 1884 KB Output is correct
8 Correct 10 ms 2140 KB Output is correct
9 Correct 8 ms 1884 KB Output is correct
10 Correct 7 ms 1884 KB Output is correct
11 Correct 6 ms 1884 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 568 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 424 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 470 ms 2140 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2904 KB Output is correct
2 Correct 7 ms 1880 KB Output is correct
3 Correct 7 ms 2368 KB Output is correct
4 Correct 7 ms 2396 KB Output is correct
5 Correct 7 ms 2140 KB Output is correct
6 Correct 7 ms 1980 KB Output is correct
7 Correct 7 ms 1884 KB Output is correct
8 Correct 8 ms 2396 KB Output is correct
9 Correct 9 ms 2896 KB Output is correct
10 Correct 7 ms 2936 KB Output is correct
11 Correct 7 ms 2908 KB Output is correct
12 Correct 8 ms 2760 KB Output is correct
13 Correct 7 ms 2136 KB Output is correct
14 Correct 8 ms 1820 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2140 KB Output is correct
2 Correct 6 ms 1884 KB Output is correct
3 Correct 8 ms 1884 KB Output is correct
4 Correct 6 ms 1884 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 5 ms 2020 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Incorrect 3 ms 1116 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2140 KB Output is correct
2 Correct 10 ms 2140 KB Output is correct
3 Correct 9 ms 2140 KB Output is correct
4 Correct 9 ms 2140 KB Output is correct
5 Correct 8 ms 1976 KB Output is correct
6 Correct 8 ms 1884 KB Output is correct
7 Correct 5 ms 1884 KB Output is correct
8 Correct 10 ms 2140 KB Output is correct
9 Correct 8 ms 1884 KB Output is correct
10 Correct 7 ms 1884 KB Output is correct
11 Correct 6 ms 1884 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 568 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 424 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Incorrect 470 ms 2140 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
33 Halted 0 ms 0 KB -