Submission #118151

#	Time	Username	Problem	Language	Result	Execution time	Memory
118151		MvC	Toy Train (IOI17_train)	C++14	11 / 100	1377 ms	2040 KiB

train

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#include "train.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=5e3+50;
const int mod=1e9+7;
using namespace std;
int tot[nmax],viz[nmax],i,j,v,nr,a[nmax],r[nmax],n,m,x,y;
vector<int>g[nmax],rg[nmax],rs;
void dfs1(int x,int b)
{
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		if(!viz[g[x][i]])
		{
			if(b)dfs1(g[x][i],b);
			else if(!b && !r[g[x][i]])dfs1(g[x][i],b);
		}
	}
}
void dfs2(int x)
{
	tot[x]=1;
	for(int i=0;i<rg[x].size();i++)if(!tot[rg[x][i]])dfs2(rg[x][i]);
}
vector<int> who_wins(vector<int>A,vector<int>R,vector<int>U,vector<int>V)
{
	n=A.size(),m=U.size();
	for(i=1;i<=n;i++)
	{
		a[i]=A[i-1];
		nr+=a[i];
	}
	for(i=1;i<=n;i++)r[i]=R[i-1];
	for(i=1;i<=m;i++)
	{
		x=U[i-1]+1,y=V[i-1]+1;
		g[x].pb(y);
		rg[y].pb(x);
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)viz[j]=0;
		dfs1(i,nr==n);
		v=0;
		for(j=0;j<rg[i].size();j++)
		{
			if(viz[rg[i][j]])
			{
				v=1;
				break;
			}
		}
		if(v)
		{
			if((nr==n && r[i]) || (!nr && !r[i]))dfs2(i);
		}
	}
	for(i=1;i<=n;i++)rs.pb(tot[i]);
	return rs;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		nr+=a[i];
	}
	for(i=1;i<=n;i++)cin>>r[i];
	for(i=1;i<=m;i++)
	{
		cin>>x>>y;
		g[x].pb(y);
		rg[y].pb(x);
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)viz[j]=0;
		dfs1(i,nr==n);
		v=0;
		for(j=0;j<rg[i].size();j++)
		{
			if(viz[rg[i][j]])
			{
				v=1;
				break;
			}
		}
		if(v)
		{
			if((nr==n && a[i]) || (!nr && !a[i]))dfs2(i);
		}
	}
	for(i=1;i<=n;i++)cout<<tot[i]<<" ";
	cout<<endl;
    return 0;
}*/

Compilation message (stderr)

train.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
train.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
train.cpp: In function 'void dfs1(int, int)':
train.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
train.cpp: In function 'void dfs2(int)':
train.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<rg[x].size();i++)if(!tot[rg[x][i]])dfs2(rg[x][i]);
              ~^~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:61:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<rg[i].size();j++)
           ~^~~~~~~~~~~~~

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