oj.uz

Submission #405767

# Submission time Handle Problem Language Result Execution time Memory
405767 2021-05-16T21:45:53 Z peuch Toy Train (IOI17_train) C++17
11 / 100
 264 ms 25080 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e5;

int n;

int marc[MAXN];
int pode[MAXN];
int	bom[MAXN];

vector<int> ar[MAXN];
vector<int> rev[MAXN];

bool haveCycle(int cur, int ori){
	marc[cur] = 1;
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == ori) return true; 
		if(marc[viz]) continue;
		if(pode[viz]) continue;
		if(haveCycle(viz, ori)) return true;
	}
	return false;
}

void dfs(int cur){
	marc[cur] = 1;
	for(int i = 0; i < rev[cur].size(); i++){
		int viz = rev[cur][i];
		if(marc[viz]) continue;
		dfs(viz);
	}
}

vector<int> sub1(std::vector<int> a, std::vector<int> r){
	vector<int> w(n, 0);
	for(int i = n - 1; i >= 0; i--){
		if(ar[i].size() == 2){
			if(a[i]){
				if(r[i]) w[i] = 1;
				else w[i] = w[i + 1];
			}
			else{
				if(r[i]) w[i] = w[i + 1];
				else w[i] = 0;
			}
		}
		else if(ar[i][0] == i) w[i] = r[i];
		else w[i] = w[i + 1];
	}
	return w;
}


vector<int> sub2(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v){
	vector<int> w(n, 0);
	return w;
}

vector<int> sub3(std::vector<int> a, std::vector<int> r){
	vector<int> w;
	for(int i = 0; i < r.size(); i++){
		if(!r[i]) continue; 
		for(int j = 0; j < r.size(); j++)
			marc[j] = 0;
		bom[i] = haveCycle(i, i);
	}
	for(int j = 0; j < n; j++)
		marc[j] = 0;
	for(int i = 0; i < n; i++)
		if(bom[i]) dfs(i);
	for(int i = 0; i < n; i++)
		w.push_back(marc[i]);
	return w;
}

vector<int> sub4(std::vector<int> a, std::vector<int> r){
	vector<int> w(n, 0);
	for(int j = 0; j < r.size(); j++)
		pode[j] = r[j];
	for(int i = 0; i < n; i++){
		if(r[i]) continue;
		for(int j = 0; j < n; j++)
			marc[j] = 0;
		bom[i] = haveCycle(i, i);
	}
	for(int j = 0; j < n; j++)
		marc[j] = 0;
	for(int i = 0; i < n; i++)
		if(bom[i]) dfs(i);
	for(int i = 0; i < n; i++)
		w.push_back(!marc[i]);
	return w;
}

vector<int> sub5(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v){
	vector<int> w(n, 0);
	return w;
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	n = a.size();
	
	for(int i = 0; i < u.size(); i++){
		ar[u[i]].push_back(v[i]);
		rev[v[i]].push_back(u[i]);
	}
	
//	if(n <= 15) return sub2(a, r, u, v); 
	
	bool flag = true;
	for(int i = 0; i < n; i++)
		flag &= a[i];
		
	if(flag) return sub3(a, r);
	
	flag = true;
	for(int i = 0; i < n; i++)
		flag &= !a[i];
		
	if(flag) return sub4(a, r);
	
	int cnt = 0;
	
	for(int i = 0; i < n; i++)
		cnt += r[i];
	
//	if(cnt == 1) return sub5(a, r, u, v);
	
	return sub1(a, r);
}

Compilation message

train.cpp: In function 'bool haveCycle(int, int)':
train.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
train.cpp: In function 'void dfs(int)':
train.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < rev[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> sub3(std::vector<int>, std::vector<int>)':
train.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < r.size(); i++){
      |                 ~~^~~~~~~~~~
train.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int j = 0; j < r.size(); j++)
      |                  ~~^~~~~~~~~~
train.cpp: In function 'std::vector<int> sub4(std::vector<int>, std::vector<int>)':
train.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int j = 0; j < r.size(); j++)
      |                 ~~^~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:106:19: 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 Correct 20 ms 24268 KB Output is correct
2 Correct 20 ms 24256 KB Output is correct
3 Correct 20 ms 24328 KB Output is correct
4 Correct 20 ms 24256 KB Output is correct
5 Correct 20 ms 24232 KB Output is correct
6 Correct 20 ms 24252 KB Output is correct
7 Incorrect 23 ms 24448 KB WA in grader: Wrong returned array size
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24772 KB Output is correct
2 Correct 46 ms 24780 KB Output is correct
3 Correct 75 ms 24916 KB Output is correct
4 Correct 154 ms 24780 KB Output is correct
5 Correct 46 ms 25024 KB Output is correct
6 Correct 97 ms 25004 KB Output is correct
7 Correct 227 ms 24864 KB Output is correct
8 Correct 24 ms 24872 KB Output is correct
9 Correct 23 ms 24892 KB Output is correct
10 Correct 26 ms 24916 KB Output is correct
11 Correct 23 ms 24780 KB Output is correct
12 Correct 23 ms 24780 KB Output is correct
13 Correct 25 ms 25036 KB Output is correct
14 Correct 25 ms 25036 KB Output is correct
15 Correct 28 ms 25076 KB Output is correct
16 Correct 24 ms 25080 KB Output is correct
17 Correct 25 ms 25072 KB Output is correct
18 Correct 264 ms 24652 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24516 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24268 KB Output is correct
2 Correct 20 ms 24256 KB Output is correct
3 Correct 20 ms 24328 KB Output is correct
4 Correct 20 ms 24256 KB Output is correct
5 Correct 20 ms 24232 KB Output is correct
6 Correct 20 ms 24252 KB Output is correct
7 Incorrect 23 ms 24448 KB WA in grader: Wrong returned array size
8 Halted 0 ms 0 KB -