Submission #56569

#	Time	Username	Problem	Language	Result	Execution time	Memory
56569		FLDutchman	Toy Train (IOI17_train)	C++14	0 / 100	2062 ms	100356 KiB

train

//#include "train.h"
#include "bits/stdc++.h"
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
using namespace std;
typedef vector<int> vi;
const int NMAX = 5010;

int N, M;
vi kind, isCharging;
vi adj[NMAX], iadj[NMAX];
bitset<NMAX> vis;
vi outdeg;

void dfs(int n){
	vis[n] = 1;
	for(int k : iadj[n]) if(!vis[k]) {
		if(kind[k] == 1 || outdeg[k] == 1) dfs(k);
		else outdeg[k]--;
	}
}

vi reaches(vi start){
	vi copy = outdeg;
	vis.reset();
	for(int n : start) if(!vis[n]) dfs(n);
	outdeg = copy;
	vi ret;
	FOR(i, 0, N) if(vis[i]) ret.pb(i);
	return ret;
}

int g[NMAX][NMAX];
vi who_wins(vi a, vi r, vi u, vi v) {
	//cout<<"Called"<<endl;
	kind = a;
	isCharging = r;
	N = a.size();
	M = u.size();
	outdeg.assign(N, 0);
	//cout<<"starting"<<endl;
	FOR(i, 0, u.size()){
		adj[u[i]].pb(v[i]);
		outdeg[u[i]]++;
		iadj[v[i]].pb(u[i]);
	}
	//cout<<1<<endl;
	memset(g, 0, NMAX*NMAX);
	//cout<<"a "<<endl;
	FOR(i, 0, N) {
		vi t = reaches({i});
		for(int j : t) g[i][j] = 1;
	}
	vi start;
	//FOR(i, 0, N) {
		//FOR(j, 0, N)cout<<g[i][j]<<" ";
		//cout<<endl;
	//} 
	FOR(i, 0, N) if(isCharging[i]) FOR(j, 0, N) {
		if(g[i][j] and g[j][i]) {
			start.pb(i);
			break;
		}
	}
	//cout << "start: " << endl;
	//for(int s : start) cout << s << " ";
	//cout<<endl;
	//cout<<"Declaring ret"<<endl;
	vi ret(N, 0);
	vi out = reaches(start);
	for(int k : out) ret[k] = 1;
	//cout<<"returning"<<endl;
	return ret;
}

/*
int main() {
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> a(n), r(n), u(m), v(m);

	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &a[i]));

	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));

	for(int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));
	
	vector<int> res = who_wins(a, r, u, v);
	
	for(int i = 0; i < (int)res.size(); i++)
		printf(i ? " %d" : "%d", res[i]);
	printf("\n");

	return 0;
}


/*
2 4
0 1
1 0
0 0
0 1
1 0
1 1

7 11
1 0 0 0 0 0 0
1 0 0 0 0 0 0
0 4
0 5
1 0
1 3
1 2
2 1
2 3
3 0
4 0
5 6
6 6

*/

Compilation message (stderr)

train.cpp:102:1: warning: "/*" within comment [-Wcomment]
 /*
  
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:3:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
train.cpp:42:2: note: in expansion of macro 'FOR'
  FOR(i, 0, u.size()){
  ^~~

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