oj.uz

Submission #1045640

# Submission time Handle Problem Language Result Execution time Memory
1045640 2024-08-06T06:40:51 Z pcc Toy Train (IOI17_train) C++17
11 / 100
 1125 ms 4436 KB 
#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];
bitset<mxn> ban;
bitset<mxn> cyc;

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]&&!ban[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();
	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;
	}
	for(auto &i:charge)ban[i] = true;
	for(int i = 0;i<N;i++){
		BFS(i);
		cyc[i] = dist[i];
	}
	/*
	cerr<<"CYC:";for(int i = 0;i<N;i++)cerr<<cyc[i];cerr<<endl;
	cerr<<"BAN:";for(int i = 0;i<N;i++)cerr<<ban[i];cerr<<endl;
	*/
	vector<int> ans(N,1);
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			if(reach[i][j]&&cyc[j])ans[i] = 0;
		}
	}
	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:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0;i<u.size();i++){
      |                ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 4020 KB 3rd lines differ - on the 14th 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 348 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 4176 KB Output is correct
2 Correct 164 ms 4068 KB Output is correct
3 Correct 152 ms 4064 KB Output is correct
4 Incorrect 1125 ms 4068 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 3948 KB Output is correct
2 Correct 182 ms 4152 KB Output is correct
3 Correct 334 ms 4252 KB Output is correct
4 Correct 377 ms 4432 KB Output is correct
5 Correct 512 ms 4436 KB Output is correct
6 Correct 456 ms 4436 KB Output is correct
7 Correct 515 ms 4436 KB Output is correct
8 Correct 360 ms 4436 KB Output is correct
9 Correct 40 ms 4188 KB Output is correct
10 Correct 532 ms 4436 KB Output is correct
11 Correct 550 ms 4432 KB Output is correct
12 Correct 550 ms 4436 KB Output is correct
13 Correct 595 ms 4268 KB Output is correct
14 Correct 343 ms 4432 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1111 ms 4052 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 Incorrect 104 ms 4020 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -