Submission #426826

#	Time	Username	Problem	Language	Result	Execution time	Memory
426826		Mounir	Toy Train (IOI17_train)	C++14	5 / 100	13 ms	3148 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define pb push_back
using namespace std;

const int N = 5005;
vector<int> voisins[2][N];
bool aMoi[N], allumee[N];
bool vu[2][N];
stack<int> ordre;
vector<vector<int>> cfcs;
int icfc[N];
set<int> voisinsDag[N];

void dfs(int noeud, int tour){
	if (vu[tour][noeud]) return;
	vu[tour][noeud] = true;

	for (int voisin : voisins[tour][noeud])
		dfs(voisin, tour);
	if (tour == 0)
		ordre.push(noeud);
	else {
		cfcs[sz(cfcs) - 1].pb(noeud);
		icfc[noeud] = sz(cfcs) - 1;
	}
}

bool allumeeDag[N], vuDag[N];
void dfsDag(int noeudDag){
	if (vuDag[noeudDag]) return;
	vuDag[noeudDag] = true;

	for (int voisinDag : voisinsDag[noeudDag]){
		dfsDag(voisinDag);
		allumeeDag[noeudDag] |= allumeeDag[voisinDag];
	}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	bool sub1 = true, sub3 = true;

	int nNoeuds = sz(a), nAretes = sz(u);
	for (int iArete = 0; iArete < nAretes; ++iArete){
		voisins[0][u[iArete]].pb(v[iArete]);
		voisins[1][v[iArete]].pb(u[iArete]);
		sub1 &= (v[iArete] == u[iArete] || v[iArete] == u[iArete] + 1);
	}

	for (int noeud = 0; noeud < nNoeuds; ++noeud){
		aMoi[noeud] = a[noeud];
		allumee[noeud] = r[noeud];
		sub3 &= aMoi[noeud];
	}

	vector<int> res(nNoeuds);

	if (sub1){
	for (int depart = 0; depart < nNoeuds; ++depart){
		res[depart] = 0;
		int noeud = depart;
		//cout << "dep " << depart << endl;

		while (true){
			bool jeReste = false, jePars = false;
			for (int voisin : voisins[0][noeud]){
				if (voisin != noeud)
					jePars = true;
				else
					jeReste = true;
			}

			if (a[noeud] == 1 && r[noeud] == 1 && jeReste){
				res[depart] = 1; break;
			}
			else if (a[noeud] == 0 && r[noeud] == 0 && jeReste)
				break;
			else if (!jePars){
				res[depart] = r[noeud];
				break;
			}
			noeud++;
		}
	}
	}

	else {
		for (int noeud = 0; noeud < nNoeuds; ++noeud)
			dfs(noeud, 0);
		while (!ordre.empty()){
			int noeud = ordre.top(); ordre.pop();
			if (!vu[1][noeud]){
				cfcs.pb({});
				dfs(noeud, 1);
			}
		}

		for (int noeud = 0; noeud < nNoeuds; ++noeud) {
			for (int voisin : voisins[0][noeud])
				voisinsDag[icfc[noeud]].insert(icfc[voisin]);
			allumeeDag[icfc[noeud]] |= allumee[noeud];
		}

		for (int noeud = 0; noeud < sz(cfcs); ++noeud)
			dfsDag(noeud);


		for (int noeud = 0; noeud < nNoeuds; ++noeud)
			res[noeud] = allumeeDag[icfc[noeud]];
	}
	return res;
}

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