Submission #58643

#	Time	Username	Problem	Language	Result	Execution time	Memory
58643		reality	Toy Train (IOI17_train)	C++17	100 / 100	667 ms	25032 KiB

train

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
#include "train.h"

vi answer;
int n;
const int N = 1e6;
vi G[N];
int deg[N];
int d[N];
vi who;

void dfs(int node) {
	for (auto it : G[node]) {
		--deg[it];
		if (!deg[it] && who[it])
			dfs(it);
	}
}

vi who_wins(vi a, vi b, vi u, vi v) {
	n = a.size();
	for (auto & it : b)
		it ^= 1;
	who = b;
	for (int i = 0;i < u.size();++i)
		G[v[i]].pb(u[i]),++d[u[i]];
	answer.resize(n);
	for (int i = 0;i < n;++i)
		answer[i] = 1;
	int ok;
	do {
		ok = 0;
		who = b;
		for (int i = 0;i < n;++i)
			deg[i] = a[i] ? 1 : d[i];
		for (int i = 0;i < n;++i)
			if (!who[i] && answer[i])
				dfs(i);
		for (int i = 0;i < n;++i) {
			if (!who[i] && answer[i] && deg[i] > 0)
				ok = 1,answer[i] = 0;
			answer[i] &= deg[i] <= 0;
		}
	} while (ok);
	return answer;
}

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:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < u.size();++i)
                 ~~^~~~~~~~~~

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