Submission #1052358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052358		Unforgettablepl	Toy Train (IOI17_train)	C++17	15 / 100	2059 ms	1368 KiB

train

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

vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v){
	int n = a.size();
	int m = u.size();
	vector<vector<int>> adj(n);
	for(int i=0;i<m;i++) {
		adj[u[i]].emplace_back(v[i]);
	}
	stack<int> special_nodes;
	special_nodes.emplace(-1);
	vector<int> tim(n,-1);
	int time = 0;
	function<int(int)> optimal_play = [&](int x)->int {
		tim[x]=++time;
		int ans = 1;
		if(r[x])special_nodes.emplace(time);
		for(int&i:adj[x]) {
			if(tim[i]!=-1) {
				if(a[x]) {
					if(tim[i]<=special_nodes.top()) {
						ans = 0;
						break;
					}
				} else {
					if(tim[i]>special_nodes.top()) {
						ans = 0;
						break;
					}
				}
			} else {
				if(optimal_play(i)==a[x]) {
					ans = 0;
					break;
				}
			}
		}
		if(r[x])special_nodes.pop();
		time--;
		tim[x]=-1;
		return a[x]^ans;
	};
	vector<int> res(n);
	for(int i=0;i<n;i++)
		res[i]=optimal_play(i);
	return res;
}

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