oj.uz

Submission #405779

# Submission time Handle Problem Language Result Execution time Memory
405779 2021-05-16T22:03:05 Z peuch Toy Train (IOI17_train) C++17
27 / 100
 398 ms 25096 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];
int in[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;
}

void bfs(int ini, vector<int> a){
	marc[ini] = 0;
	bom[ini] = 0;
	for(int i = 0; i < n; i++)
		in[i] = ar[i].size();
	queue<int> fila;
	fila.push(ini);
	while(!fila.empty()){
		int cur = fila.front();
		fila.pop();
		if(cur == ini) continue;
		for(int i = 0; i < rev[cur].size(); i++){
			int viz = rev[cur][i];
			if(marc[viz]) continue;
			if(!a[viz]) in[viz]--;
			if(!a[viz] && in[viz] != 0) continue;
			marc[viz] = 1;
			bom[viz] = 1;
			fila.push(viz);
		}
	}
	
}

vector<int> sub5(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v){
	vector<int> w (n, 0);
	int especial;
	for(int i = 0; i < n; i++)
		if(r[i]) especial = i;
	
	bfs(especial, a);
	
	if(!bom[especial]) return w;
	for(int i = 0; i < n; i++)
		w[i] = bom[i];
	
	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:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
train.cpp: In function 'void dfs(int)':
train.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  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:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < r.size(); i++){
      |                 ~~^~~~~~~~~~
train.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int j = 0; j < r.size(); j++)
      |                  ~~^~~~~~~~~~
train.cpp: In function 'std::vector<int> sub4(std::vector<int>, std::vector<int>)':
train.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int j = 0; j < r.size(); j++)
      |                 ~~^~~~~~~~~~
train.cpp: In function 'void bfs(int, std::vector<int>)':
train.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i = 0; i < rev[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
train.cpp: In function 'std::vector<int> sub5(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:131:18: warning: 'especial' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |  if(!bom[especial]) return w;
      |      ~~~~~~~~~~~~^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24352 KB Output is correct
2 Correct 20 ms 24344 KB Output is correct
3 Correct 23 ms 24304 KB Output is correct
4 Correct 20 ms 24328 KB Output is correct
5 Correct 20 ms 24336 KB Output is correct
6 Correct 20 ms 24264 KB Output is correct
7 Correct 24 ms 24396 KB Output is correct
8 Correct 21 ms 24396 KB Output is correct
9 Correct 19 ms 24268 KB Output is correct
10 Correct 20 ms 24188 KB Output is correct
11 Correct 19 ms 24316 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 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 24780 KB Output is correct
2 Correct 46 ms 24852 KB Output is correct
3 Correct 76 ms 24840 KB Output is correct
4 Correct 161 ms 24780 KB Output is correct
5 Correct 44 ms 24900 KB Output is correct
6 Correct 96 ms 24780 KB Output is correct
7 Correct 230 ms 24812 KB Output is correct
8 Correct 24 ms 24896 KB Output is correct
9 Correct 23 ms 24932 KB Output is correct
10 Correct 29 ms 24844 KB Output is correct
11 Correct 23 ms 24772 KB Output is correct
12 Correct 23 ms 24780 KB Output is correct
13 Correct 25 ms 25080 KB Output is correct
14 Correct 28 ms 25020 KB Output is correct
15 Correct 24 ms 25096 KB Output is correct
16 Correct 24 ms 25092 KB Output is correct
17 Correct 24 ms 25036 KB Output is correct
18 Correct 233 ms 24804 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24620 KB Output is correct
2 Correct 141 ms 24592 KB Output is correct
3 Correct 235 ms 24904 KB Output is correct
4 Correct 49 ms 24744 KB Output is correct
5 Correct 398 ms 24688 KB Output is correct
6 Correct 327 ms 24652 KB Output is correct
7 Correct 320 ms 24676 KB Output is correct
8 Correct 159 ms 24644 KB Output is correct
9 Correct 23 ms 24700 KB Output is correct
10 Correct 24 ms 24748 KB Output is correct
11 Correct 24 ms 24780 KB Output is correct
12 Correct 24 ms 24692 KB Output is correct
13 Correct 377 ms 24744 KB Output is correct
14 Correct 263 ms 24656 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24864 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 24352 KB Output is correct
2 Correct 20 ms 24344 KB Output is correct
3 Correct 23 ms 24304 KB Output is correct
4 Correct 20 ms 24328 KB Output is correct
5 Correct 20 ms 24336 KB Output is correct
6 Correct 20 ms 24264 KB Output is correct
7 Correct 24 ms 24396 KB Output is correct
8 Correct 21 ms 24396 KB Output is correct
9 Correct 19 ms 24268 KB Output is correct
10 Correct 20 ms 24188 KB Output is correct
11 Correct 19 ms 24316 KB Output is correct
12 Incorrect 14 ms 23756 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -