Submission #1045561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1045561	2024-08-06T05:45:34 Z	pcc	Toy Train (IOI17_train)	C++17	11 / 100	536 ms	4440 KB

train

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

const int mxn = 5050;

vector<int> charge;
int N,M;
queue<int> q;
int owner[mxn];
bitset<mxn> reach[mxn],dist;
vector<int> paths[mxn];

void BFS(int s = -1){
	if(s != -1){
		dist.reset();
		q.push(s);
	}
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		for(auto nxt:paths[now]){
			if(!dist[nxt]){
				dist[nxt] = 1;
				q.push(nxt);
			}
		}
	}
	return;
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	N = a.size();
	assert(r.size() == a.size());
	for(int i = 0;i<N;i++){
		owner[i] = a[i];
		if(r[i])charge.push_back(i);
	}
	for(int i = 0;i<u.size();i++){
		int aa = u[i],bb = v[i];
		paths[aa].push_back(bb);
	}
	for(int i = 0;i<N;i++){
		BFS(i);
		reach[i] = dist;
	}
	vector<int> ans(N);
	for(int i = 0;i<N;i++){
		for(auto &j:charge){
			if(reach[i][j]&&reach[j][j])ans[i] = 1;
		}
	}
	return ans;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0;i<u.size();i++){
      |                ~^~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	91 ms	3796 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	4180 KB	Output is correct
2	Correct	84 ms	4076 KB	Output is correct
3	Correct	95 ms	4072 KB	Output is correct
4	Correct	507 ms	4064 KB	Output is correct
5	Correct	423 ms	4428 KB	Output is correct
6	Correct	283 ms	4436 KB	Output is correct
7	Correct	300 ms	4436 KB	Output is correct
8	Correct	213 ms	4440 KB	Output is correct
9	Correct	178 ms	4212 KB	Output is correct
10	Correct	231 ms	4436 KB	Output is correct
11	Correct	201 ms	4184 KB	Output is correct
12	Correct	18 ms	4172 KB	Output is correct
13	Correct	527 ms	4252 KB	Output is correct
14	Correct	528 ms	4268 KB	Output is correct
15	Correct	536 ms	4256 KB	Output is correct
16	Correct	510 ms	4272 KB	Output is correct
17	Correct	495 ms	4268 KB	Output is correct
18	Correct	144 ms	4180 KB	Output is correct