Submission #826450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
826450	2023-08-15T15:14:41 Z	tolbi	Toy Train (IOI17_train)	C++17	11 / 100	1180 ms	1312 KB

train

#include <bits/stdc++.h>
using namespace std;
#include "train.h"

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n = a.size();
	int m = u.size();
	vector<vector<int>> arr(n);
	for (int i = 0; i < m; ++i)
	{
		arr[u[i]].push_back(v[i]);
	}
	for (int tar = 0; tar < n; tar++){
		vector<bool> vis(n,false);
		vector<bool> res(n,false);
		res[tar]=true;
		if (!r[tar]) continue;
		function<bool(int)> dfs;
		dfs = [&](int node)->bool{
			if (vis[node]) return res[node];
			vis[node]=true;
			int sz = 0;
			for (int i = 0; i < arr[node].size(); i++){
				if (dfs(arr[node][i])) sz++;
			}
			if ((sz>=1 && a[node]) || sz==arr[node].size()) res[node]=true;
			return res[node];
		};
		int sz = 0;
		for (int j = 0; j < arr[tar].size(); j++){
			if (dfs(arr[tar][j])) sz++;
		}
		if ((sz>=1 && a[tar]) || sz==arr[tar].size()) r[tar]=true;
		else r[tar]=false;
	}
	for (int iter = 0; iter < n; iter++){
		for (int node = 0; node < n; node++){
			if (r[node]) continue;
			int sz = 0;
			for (int i = 0; i < arr[node].size(); i++){
				if (r[arr[node][i]]) sz++;
			}
			if ((a[node] && sz>0) || sz==arr[node].size()){
				r[node]=1;
				break;
			}
		}
	}
	return r;
}

Compilation message

train.cpp: In lambda function:
train.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
train.cpp:26:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    if ((sz>=1 && a[node]) || sz==arr[node].size()) res[node]=true;
      |                              ~~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int j = 0; j < arr[tar].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~
train.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if ((sz>=1 && a[tar]) || sz==arr[tar].size()) r[tar]=true;
      |                            ~~^~~~~~~~~~~~~~~~~
train.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
train.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if ((a[node] && sz>0) || sz==arr[node].size()){
      |                             ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	176 ms	1108 KB	3rd lines differ - on the 26th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 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	147 ms	1116 KB	Output is correct
2	Correct	163 ms	1204 KB	Output is correct
3	Correct	195 ms	1304 KB	Output is correct
4	Correct	409 ms	1276 KB	Output is correct
5	Correct	87 ms	1132 KB	Output is correct
6	Correct	332 ms	1056 KB	Output is correct
7	Correct	329 ms	1008 KB	Output is correct
8	Correct	71 ms	1020 KB	Output is correct
9	Correct	168 ms	980 KB	Output is correct
10	Correct	48 ms	984 KB	Output is correct
11	Correct	60 ms	956 KB	Output is correct
12	Correct	217 ms	852 KB	Output is correct
13	Correct	20 ms	1308 KB	Output is correct
14	Correct	20 ms	1312 KB	Output is correct
15	Correct	19 ms	1312 KB	Output is correct
16	Correct	19 ms	1236 KB	Output is correct
17	Correct	20 ms	1296 KB	Output is correct
18	Correct	250 ms	1128 KB	Output is correct