oj.uz

Submission #775725

# Submission time Handle Problem Language Result Execution time Memory
775725 2023-07-06T20:19:12 Z APROHACK Toy Train (IOI17_train) C++14
28 / 100
 136 ms 1664 KB 
#include "train.h"
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define ff first
#define ss second
using namespace std;
int contNode[5001];
bool isFA[5001];
bool isFB[5001];
bool owner[5001], rechargable[5001], vis[5001];
bool answered[5001];
vector<int>adj[5001], inv[5001];
int n, m;

void restart(){
	for(int i = 0 ; i < n; i ++){
		isFA[i] = false;
		isFB[i] = false;
		vis[i] = false;
		contNode[i] = 0;
	}
}
void restart2(){
	for(int i = 0 ; i < n; i ++){
		//isFA[i] = false;
		//isFB[i] = false;
		vis[i] = false;
		contNode[i] = 0;
	}
}
void getA(){
	queue<int>llegado;
	for(int i = 0 ; i < n ;i ++){
		if(rechargable[i] and !answered[i]){
			llegado.push(i);
			isFA[i] = true;
			vis[i] = true;
		}
	}
	//cout << "fa" << endl;
	while(!llegado.empty()){
		int cur = llegado.front();
		llegado.pop();
		int v;
		for(int i = 0 ; i < inv[cur].size() ; i ++){
			v = inv[cur][i];
			if(vis[v] or answered[v])continue;
			if(owner[v] or contNode[v] + 1 == adj[v].size()){
				llegado.push(v);
				isFA[v] = true;
				vis[v] = true;
				//cout << v << endl;
			}else contNode[v] ++;
		}
	}
	//cout << endl;
}
void getB(){
	queue<int>llegado;
	for(int i = 0 ; i < n ; i ++){
		if(!isFA[i] and !answered[i]){
			isFB[i] = true;
			llegado.push(i);
			vis[i] = true;
		}
	}
	while(!llegado.empty()){
		int cur = llegado.front();
		llegado.pop();
		int v;
		for(int i = 0 ; i < inv[cur].size() ; i ++){
			v = inv[cur][i];
			if(vis[v] or answered[v])continue;
			if(!owner[v] or contNode[v] + 1 == adj[v].size()){
				llegado.push(v);
				isFB[v] = true;
				vis[v] = true;
			}else contNode[v] ++;
		}
	}
	
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	n = r.size();
	m = u.size();
	vector<int>ans;
	for(int i = 0 ; i < n ;i ++){
		owner[i] = a[i];
		rechargable[i] = r[i];
		ans.pb(1);
	}
	for(int i = 0 ; i < m ; i ++){
		adj[u[i]].pb(v[i]);
		inv[v[i]].pb(u[i]);
	}
	do{
		restart();
		getA();
		restart2();
		getB();
		bool quedo = false;
		//cout << "Fb(x) = ";
		for(int i = 0 ; i < n ; i ++){
			if(!answered[i] and isFB[i]){
				//cout << i << " " ;
				answered[i] = true;
				quedo = true;
				ans[i] = 0;
			}
		}
		//cout << endl;
		if(!quedo)return ans;
	}while(true);

}

Compilation message

train.cpp: In function 'void getA()':
train.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0 ; i < inv[cur].size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~~~~
train.cpp:49:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    if(owner[v] or contNode[v] + 1 == adj[v].size()){
      |                   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
train.cpp: In function 'void getB()':
train.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0 ; i < inv[cur].size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~~~~
train.cpp:75:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    if(!owner[v] or contNode[v] + 1 == adj[v].size()){
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 4 ms 1108 KB Output is correct
3 Correct 5 ms 1108 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 4 ms 1108 KB Output is correct
8 Correct 4 ms 1108 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1060 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 540 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 520 KB Output is correct
8 Incorrect 1 ms 468 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1664 KB Output is correct
2 Correct 103 ms 1656 KB Output is correct
3 Correct 136 ms 1656 KB Output is correct
4 Correct 6 ms 1576 KB Output is correct
5 Incorrect 6 ms 1580 KB 3rd lines differ - on the 11th token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1368 KB Output is correct
2 Correct 8 ms 1492 KB Output is correct
3 Correct 8 ms 1580 KB Output is correct
4 Correct 6 ms 1620 KB Output is correct
5 Correct 6 ms 1620 KB Output is correct
6 Correct 6 ms 1492 KB Output is correct
7 Correct 6 ms 1492 KB Output is correct
8 Correct 5 ms 1492 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 6 ms 1620 KB Output is correct
11 Correct 6 ms 1572 KB Output is correct
12 Correct 6 ms 1620 KB Output is correct
13 Correct 6 ms 1560 KB Output is correct
14 Correct 6 ms 1492 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1580 KB Output is correct
2 Correct 6 ms 1620 KB Output is correct
3 Correct 6 ms 1620 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 1 ms 552 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 4 ms 1236 KB Output is correct
8 Correct 4 ms 1324 KB Output is correct
9 Correct 4 ms 1212 KB Output is correct
10 Correct 1 ms 684 KB Output is correct
11 Correct 5 ms 1108 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 4 ms 1108 KB Output is correct
3 Correct 5 ms 1108 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 4 ms 1108 KB Output is correct
8 Correct 4 ms 1108 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1060 KB Output is correct
12 Correct 1 ms 540 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 520 KB Output is correct
19 Incorrect 1 ms 468 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
20 Halted 0 ms 0 KB -