oj.uz

Submission #405768

# Submission time Handle Problem Language Result Execution time Memory
405768 2021-05-16T21:46:19 Z peuch Toy Train (IOI17_train) C++17
27 / 100
 394 ms 25060 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;
	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24268 KB Output is correct
2 Correct 21 ms 24268 KB Output is correct
3 Correct 20 ms 24268 KB Output is correct
4 Correct 20 ms 24340 KB Output is correct
5 Correct 20 ms 24312 KB Output is correct
6 Correct 20 ms 24268 KB Output is correct
7 Correct 21 ms 24436 KB Output is correct
8 Correct 22 ms 24404 KB Output is correct
9 Correct 20 ms 24268 KB Output is correct
10 Correct 20 ms 24300 KB Output is correct
11 Correct 19 ms 24200 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23720 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 29 ms 24780 KB Output is correct
2 Correct 46 ms 24812 KB Output is correct
3 Correct 80 ms 24780 KB Output is correct
4 Correct 154 ms 24772 KB Output is correct
5 Correct 45 ms 24748 KB Output is correct
6 Correct 97 ms 24656 KB Output is correct
7 Correct 230 ms 24688 KB Output is correct
8 Correct 24 ms 24652 KB Output is correct
9 Correct 24 ms 24724 KB Output is correct
10 Correct 26 ms 24668 KB Output is correct
11 Correct 24 ms 24636 KB Output is correct
12 Correct 23 ms 24616 KB Output is correct
13 Correct 25 ms 24864 KB Output is correct
14 Correct 24 ms 24780 KB Output is correct
15 Correct 24 ms 24804 KB Output is correct
16 Correct 24 ms 24868 KB Output is correct
17 Correct 25 ms 24756 KB Output is correct
18 Correct 209 ms 24564 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24580 KB Output is correct
2 Correct 152 ms 24760 KB Output is correct
3 Correct 220 ms 24860 KB Output is correct
4 Correct 50 ms 24904 KB Output is correct
5 Correct 394 ms 25032 KB Output is correct
6 Correct 321 ms 24900 KB Output is correct
7 Correct 367 ms 24856 KB Output is correct
8 Correct 161 ms 24816 KB Output is correct
9 Correct 23 ms 24780 KB Output is correct
10 Correct 26 ms 24940 KB Output is correct
11 Correct 24 ms 24952 KB Output is correct
12 Correct 27 ms 24908 KB Output is correct
13 Correct 370 ms 25060 KB Output is correct
14 Correct 260 ms 24808 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24652 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 21 ms 24268 KB Output is correct
3 Correct 20 ms 24268 KB Output is correct
4 Correct 20 ms 24340 KB Output is correct
5 Correct 20 ms 24312 KB Output is correct
6 Correct 20 ms 24268 KB Output is correct
7 Correct 21 ms 24436 KB Output is correct
8 Correct 22 ms 24404 KB Output is correct
9 Correct 20 ms 24268 KB Output is correct
10 Correct 20 ms 24300 KB Output is correct
11 Correct 19 ms 24200 KB Output is correct
12 Incorrect 16 ms 23720 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -