oj.uz

Submission #56569

# Submission time Handle Problem Language Result Execution time Memory
56569 2018-07-11T18:07:24 Z FLDutchman Toy Train (IOI17_train) C++14
0 / 100
 2000 ms 100356 KB 
//#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

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

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 100356 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 100356 KB Output is correct
2 Execution timed out 2062 ms 100356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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