Submission #420783

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
420783	2021-06-08T13:54:20 Z	AugustinasJucas	Toy Train (IOI17_train)	C++14	0 / 100	2000 ms	1116 KB

train


#include "train.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> charg;
vector<int> priklauso;
int n;
const int dydis = 5e3 + 10;
bool vis[dydis] = {};
bool can[dydis] = {};
int onS[dydis] = {};
bool can1[dydis] = {};
vector<int> gr[dydis];
bool dfs(int v){
	if(onS[v]) return 0;
	if(vis[v]) return can[v];
	vis[v] = 1;
	if(charg[v]) {
		can[v] = 1;
		return 1;
	}
	//cout << "dfs, v = " << v << endl;
	bool ret = 0;
	for(auto x : gr[v]){
		onS[v]++;
		ret = ret | dfs(x);
		onS[v]--;
	}
	can[v] = ret;
	return ret;
}
bool dfs1(int v){
	if(onS[v]) return 0;
	if(vis[v]) return can1[v];
	vis[v] = 1;
	if(can[v]) {
		can1[v] = 1;
		return 1;
	}

	bool ret = 0;
	for(auto x : gr[v]){
		onS[x]++;
		ret = ret | dfs1(x);
		onS[x]--;
	}
	can1[v] = ret;
	return ret;
}
vector<int> viskasPirmo(){
	vector<int> ret(n, 0);
	
	for(int i = 0; i < n; i++){ // pradedu i
		for(int j = 0; j < n; j++) vis[j] = onS[j] = can[j] = can1[j] = 0;
	//	cout << "i = " << i << endl;
		dfs(i);

	//	cout << "gaunam, kad pasiekti ch gales: "; for(int j = 0; j < n; j++) if(can[j]) cout << j << ", "; cout << endl;
		for(int j = 0; j < n; j++) vis[j] = onS[j] = 0;
		for(int j = 0; j < n; j++) if(charg[j]) can[j] = 0;
		for(int j = 0; j < n; j++) if(charg[j]) ret[i] = ret[i] || dfs1(j);
	}	
	return ret;
}
vector<int> viskasAntro(){
	vector<int> ret(n);
	return ret;
}
vector<int> vienCharg(){
	vector<int> ret(n);
	return ret;
}
vector<bool> isEnd(5001, 0);
vector<int> prm(){
	vector<int> ret(n, 0);

	for(int i = 0; i < n; i++){
		int v = i;
	//	cout << "i  = " << i << endl;
		while(true){
		//	cout << "v = " << v << ", end = " << isEnd[v] << endl;
			if(isEnd[v] && priklauso[v] == charg[v]){
			//	cout << v << " priklauso " << priklauso[v] << endl;
				ret[i] = priklauso[v];
				break;
			}else{
				v = gr[v][0];
			}
		}
	}
	return ret;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	vector<int> res(a.size());
	priklauso = a;
	charg = r;
	n = a.size();
	for(int i = 0; i < (int)u.size(); i++){
		gr[u[i]].push_back(v[i]);
	//	gr[v[i]].push_back(u[i]);
	}
	int cnt[2] = {0}; for(auto x : a) cnt[x]++;
	int rc = 0; for(auto x : r) rc += x;
	bool pirmasSub = 1;
	for(int i = 0 ; i < u.size(); i++) {
		if(v[i] == u[i]) isEnd[v[i]] = 1;
		if(v[i] - u[i] == 0 || v[i]-u[i] == 1) continue;
		pirmasSub = 0;
	}
	if(pirmasSub){
		return prm();
	}
	if(cnt[1] == 0){
		return viskasPirmo();
	}else if(cnt[0] == 0){
		return viskasAntro();
	}else if(rc == 0){
		return vienCharg();
	}
	//for(int i = 0; i < n; i++)
	
	return res;
}

Compilation message

train.cpp: In function 'std::vector<int> viskasPirmo()':
train.cpp:55:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   55 |   for(int j = 0; j < n; j++) vis[j] = onS[j] = can[j] = can1[j] = 0;
      |                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
train.cpp:60:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   60 |   for(int j = 0; j < n; j++) vis[j] = onS[j] = 0;
      |                                       ~~~~~~~^~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i = 0 ; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2068 ms	716 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1100 KB	Output is correct
2	Correct	7 ms	1092 KB	Output is correct
3	Correct	7 ms	1116 KB	Output is correct
4	Incorrect	7 ms	1100 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-