Submission #249952

#	Time	Username	Problem	Language	Result	Execution time	Memory
249952		kostia244	Toy Train (IOI17_train)	C++17	5 / 100	923 ms	2296 KiB

train

#include "train.h"
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,sse,sse2,avx2,ssse3,tune=native")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5050;
int n, m, w[maxn], loop[maxn];
array<int, maxn> dist;
vector<int> g[maxn], a, r, res;
std::vector<int> who_wins(std::vector<int> _a, std::vector<int> _r, std::vector<int> u, std::vector<int> v) {
	n = _a.size();
	m = u.size();
	a = _a, r = _r;
	for(int i = 0; i < m; i++) {
		if(u[i] != v[i])
			g[u[i]].push_back(v[i]);
		else loop[u[i]] = 1;
	}
	for(int i = 0; i < n; i++)
		dist[i] = 0;
	for(int iter = 0; iter <= n; iter++) {
		array<int, maxn> ndist;
		for(int i = 0; i < n; i++) {
			if(r[i]) {
				ndist[i] = 0;
				continue;
			}
			if(a[i]) {
				ndist[i] = 1<<30;
				for(auto j : g[i]) 
					if(!r[j]) ndist[i] = min(ndist[i], dist[j]+1);
					else ndist[i] = 0;
			} else {
				ndist[i] = loop[i] ? 1<<30 : 0;
				for(auto j : g[i]) if(!r[j]) ndist[i] = max(ndist[i], dist[j]+1);
			}
		}
		dist = ndist;
	}
	for(int i = 0; i < n; i++) {
		if(dist[i] > n) w[i] = -1;
		if(a[i]) {
			if(loop[i] && r[i]) w[i] = 1;
		} else {
			if(loop[i] && !r[i]) w[i] = -1;
		}
	}
	for(int iter = 0; iter <= n; iter++) {
		for(int i = 0; i < n; i++) if(!w[i]) {
			int p = 0, n = 0;
			for(auto j : g[i]) {
				p += w[j] == 1;
				n += w[j] == -1;
			}
			if(a[i]) {
				if(n == g[i].size()) w[i] = -1;
				if(p) w[i] = 1;
			} else {
				if(p == g[i].size()) w[i] = 1;
				if(n) w[i] = -1;
			}
		}
	}
	for(int i = 0; i < n; i++) {
		assert(w[i] != 0);
		res.push_back(max(0, w[i]));
	}
	return res;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:56:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(n == g[i].size()) w[i] = -1;
        ~~^~~~~~~~~~~~~~
train.cpp:59:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p == g[i].size()) w[i] = 1;
        ~~^~~~~~~~~~~~~~
train.cpp:38:8: warning: 'ndist' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dist = ndist;
   ~~~~~^~~~~~~

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