Submission #980082

#	Time	Username	Problem	Language	Result	Execution time	Memory
980082		hyakup	Toy Train (IOI17_train)	C++17	23 / 100	1455 ms	100068 KiB

train

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

const int maxn = 5e3 + 10;
vector<int> adj[2][maxn], special, dono, marc( maxn );
int dp[maxn][maxn];

void solve( int cur ){
	for( int i = 0; i < marc.size(); i++ ) marc[i] = 0;
	queue<int> fila;
	for( int viz : adj[1][cur] ){
		if( dono[viz] ) fila.push(viz), dp[viz][cur] = 1;
		else{
			marc[viz]++;
			if( marc[viz] == adj[0][viz].size() ) fila.push(viz), dp[viz][cur] = 1;
		}
	}
	while( !fila.empty() ){
		int x = fila.front(); fila.pop();
		for( int viz : adj[1][x] ){
			if( dono[viz] ){ if( !dp[viz][cur] ) fila.push(viz), dp[viz][cur] = 1;}
			else{
				marc[viz]++;
				if( marc[viz] == adj[0][viz].size() ) fila.push(viz), dp[viz][cur] = 1;
			}
		}
	}
}


vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
 	special = r; dono = a;
	int n = a.size();
	for( int i = 0; i < u.size(); i++ ){
		adj[0][u[i]].push_back(v[i]);
		adj[1][v[i]].push_back(u[i]);
	}
	for( int i = 0; i < n; i++ ) solve(i);
	vector<int> resp;
	for( int i = 0; i < n; i++ ){
		resp.push_back(0);
		for( int j = 0; j < n; j++ ) if( special[j] && dp[i][j] && dp[j][j] ) resp[i] = 1;
	}
	return resp;
}

Compilation message (stderr)

train.cpp: In function 'void solve(int)':
train.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for( int i = 0; i < marc.size(); i++ ) marc[i] = 0;
      |                  ~~^~~~~~~~~~~~~
train.cpp:16:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |    if( marc[viz] == adj[0][viz].size() ) fila.push(viz), dp[viz][cur] = 1;
train.cpp:25:19: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if( marc[viz] == adj[0][viz].size() ) fila.push(viz), dp[viz][cur] = 1;
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for( int i = 0; i < u.size(); i++ ){
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 12 / 12
• Subtask 6: 0 / 51