Submission #99216

#	Time	Username	Problem	Language	Result	Execution time	Memory
99216		eriksuenderhauf	Toy Train (IOI17_train)	C++11	100 / 100	536 ms	1532 KiB

train

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "train.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e3 + 5;
const double eps = 1e-9;
vi adj[MAXN];
int deg[MAXN], cnt[MAXN];

void dfs(int u, vi& r) {
	for (int v: adj[u])
    {
        cnt[v]--;
        if (r[v] == 1 || cnt[v] != 0)
            continue;
		dfs(v, r);
	}
}

vi who_wins(vi a, vi r, vi u, vi v) {
	int n = a.size(), m = u.size();
	for (int i = 0; i < m; i++)
        adj[v[i]].pb(u[i]), deg[u[i]]++;
	vi ans;
	for (int i = 0; i < n; i++) ans.pb(1);
	while (1)
    {
        for (int i = 0; i < n; i++)
            cnt[i] = a[i] == 1 ? 1 : deg[i];
        for (int i = 0; i < n; i++)
            if (r[i] == 1 && ans[i] == 1)
                dfs(i, r);
        int fl = 0;
        for (int i = 0; i < n; i++)
            if (r[i] == 1 && ans[i] == 1 && cnt[i] > 0)
                ans[i] = 0, fl = 1;
        if (fl == 0)
            break;
	}
	for (int i = 0; i < n; i++)
        ans[i] &= cnt[i] <= 0;
	return ans;
}

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