oj.uz

Submission #405784

# Submission time Handle Problem Language Result Execution time Memory
405784 2021-05-16T22:29:59 Z peuch Toy Train (IOI17_train) C++17
39 / 100
 403 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];
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] = 1;
	bom[ini] = 1;
	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();
		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);
	
	bool orFlag = false;
	bool andFlag = true;
	for(int i = 0; i < ar[especial].size(); i++){
		int viz = ar[especial][i];
		orFlag |= bom[viz];
		andFlag &= bom[viz];
	}
	if(a[especial] && !orFlag) return w;
	if(!a[especial] && !andFlag) 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:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int i = 0; i < rev[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> sub5(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |  for(int i = 0; i < ar[especial].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:148:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  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:137:15: warning: 'especial' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |  if(a[especial] && !orFlag) return w;
      |               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24396 KB Output is correct
2 Correct 19 ms 24232 KB Output is correct
3 Correct 19 ms 24348 KB Output is correct
4 Correct 19 ms 24340 KB Output is correct
5 Correct 19 ms 24256 KB Output is correct
6 Correct 19 ms 24332 KB Output is correct
7 Correct 21 ms 24388 KB Output is correct
8 Correct 22 ms 24396 KB Output is correct
9 Correct 19 ms 24268 KB Output is correct
10 Correct 22 ms 24308 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 17 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 27 ms 24784 KB Output is correct
2 Correct 45 ms 24796 KB Output is correct
3 Correct 86 ms 24908 KB Output is correct
4 Correct 155 ms 24908 KB Output is correct
5 Correct 46 ms 24748 KB Output is correct
6 Correct 98 ms 24692 KB Output is correct
7 Correct 234 ms 24924 KB Output is correct
8 Correct 24 ms 24652 KB Output is correct
9 Correct 23 ms 24664 KB Output is correct
10 Correct 36 ms 24684 KB Output is correct
11 Correct 23 ms 24616 KB Output is correct
12 Correct 22 ms 24664 KB Output is correct
13 Correct 23 ms 24840 KB Output is correct
14 Correct 24 ms 24884 KB Output is correct
15 Correct 24 ms 24876 KB Output is correct
16 Correct 25 ms 24832 KB Output is correct
17 Correct 23 ms 24880 KB Output is correct
18 Correct 211 ms 24628 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24524 KB Output is correct
2 Correct 143 ms 24632 KB Output is correct
3 Correct 222 ms 24664 KB Output is correct
4 Correct 50 ms 24652 KB Output is correct
5 Correct 403 ms 24712 KB Output is correct
6 Correct 330 ms 24760 KB Output is correct
7 Correct 325 ms 24668 KB Output is correct
8 Correct 156 ms 24644 KB Output is correct
9 Correct 22 ms 24584 KB Output is correct
10 Correct 24 ms 24708 KB Output is correct
11 Correct 23 ms 24668 KB Output is correct
12 Correct 24 ms 24724 KB Output is correct
13 Correct 373 ms 24804 KB Output is correct
14 Correct 256 ms 24708 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24780 KB Output is correct
2 Correct 26 ms 25072 KB Output is correct
3 Correct 23 ms 25080 KB Output is correct
4 Correct 22 ms 24952 KB Output is correct
5 Correct 15 ms 23884 KB Output is correct
6 Correct 19 ms 24468 KB Output is correct
7 Correct 22 ms 24568 KB Output is correct
8 Correct 21 ms 24652 KB Output is correct
9 Correct 20 ms 24692 KB Output is correct
10 Correct 16 ms 23972 KB Output is correct
11 Correct 22 ms 24520 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24396 KB Output is correct
2 Correct 19 ms 24232 KB Output is correct
3 Correct 19 ms 24348 KB Output is correct
4 Correct 19 ms 24340 KB Output is correct
5 Correct 19 ms 24256 KB Output is correct
6 Correct 19 ms 24332 KB Output is correct
7 Correct 21 ms 24388 KB Output is correct
8 Correct 22 ms 24396 KB Output is correct
9 Correct 19 ms 24268 KB Output is correct
10 Correct 22 ms 24308 KB Output is correct
11 Correct 19 ms 24200 KB Output is correct
12 Incorrect 17 ms 23756 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -