Submission #59168

#	Time	Username	Problem	Language	Result	Execution time	Memory
59168		TadijaSebez	Toy Train (IOI17_train)	C++11	100 / 100	620 ms	15648 KiB

train

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
#define pb push_back
const int N=5050;
vector<int> R[N];
int deg[N],in[N];
bool was[N],vis[N],A[N];
void AddEdge(int u, int v){ R[v].pb(u);deg[u]++;}
void DelNode(int u){ for(int i=0;i<R[u].size();i++) deg[R[u][i]]--;was[u]=1;}
void init(int n){ for(int i=1;i<=n;i++) vis[i]=0;}
queue<int> q;
vector<int> st;
void BFS(int n, bool mod)
{
	init(n);
	int i;
	for(i=1;i<=n;i++) if(!was[i]) in[i]=(A[i]==mod)?1:deg[i];
	for(i=0;i<st.size();i++) vis[st[i]]=1,q.push(st[i]);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(i=0;i<R[u].size();i++)
		{
			int v=R[u][i];
			if(vis[v] || was[v]) continue;
			in[v]--;
			if(!in[v])
			{
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
vector<int> ch;
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	int n=a.size(),i,m=v.size();
	for(i=0;i<n;i++) A[i+1]=a[i];
	for(i=0;i<n;i++) if(r[i]) ch.pb(i+1);
	for(i=0;i<m;i++) AddEdge(u[i]+1,v[i]+1);
	bool done;
	do
	{
		st.clear();
		for(i=0;i<ch.size();i++) if(!was[ch[i]]) st.pb(ch[i]);
		BFS(n,1);
		st.clear();
		for(i=1;i<=n;i++) if(!was[i] && !vis[i]) st.pb(i);
		BFS(n,0);
		done=0;
		for(i=1;i<=n;i++) if(!was[i] && vis[i]) done=1,DelNode(i);
	}while(done);
	vector<int> ans;
	for(i=1;i<=n;i++) ans.pb(!was[i]);
	return ans;
}
/*int main()
{
	int n,m,i,x,y;
	vector<int> a,r,u,v;
	scanf("%i %i",&n,&m);
	for(i=0;i<n;i++) scanf("%i",&x),a.pb(x);
	for(i=0;i<n;i++) scanf("%i",&x),r.pb(x);
	for(i=0;i<m;i++) scanf("%i %i",&x,&y),u.pb(x),v.pb(y);
	vector<int> ans=who_wins(a,r,u,v);
	for(i=0;i<ans.size();i++) printf("%i ",ans[i]);printf("\n");
	return 0;
}*/

Compilation message (stderr)

train.cpp: In function 'void DelNode(int)':
train.cpp:11:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 void DelNode(int u){ for(int i=0;i<R[u].size();i++) deg[R[u][i]]--;was[u]=1;}
                                  ~^~~~~~~~~~~~
train.cpp: In function 'void BFS(int, bool)':
train.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<st.size();i++) vis[st[i]]=1,q.push(st[i]);
          ~^~~~~~~~~~
train.cpp:25:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<R[u].size();i++)
           ~^~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:49:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<ch.size();i++) if(!was[ch[i]]) st.pb(ch[i]);
           ~^~~~~~~~~~

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