oj.uz

Submission #426826

# Submission time Handle Problem Language Result Execution time Memory
426826 2021-06-14T10:11:24 Z Mounir Toy Train (IOI17_train) C++14
5 / 100
 13 ms 3148 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1228 KB Output is correct
2 Correct 5 ms 1252 KB Output is correct
3 Correct 5 ms 1228 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 5 ms 1228 KB Output is correct
6 Correct 5 ms 1228 KB Output is correct
7 Correct 6 ms 1228 KB Output is correct
8 Correct 5 ms 1228 KB Output is correct
9 Correct 5 ms 1228 KB Output is correct
10 Correct 5 ms 1228 KB Output is correct
11 Correct 4 ms 1228 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 716 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3148 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1740 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1856 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1228 KB Output is correct
2 Correct 5 ms 1252 KB Output is correct
3 Correct 5 ms 1228 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 5 ms 1228 KB Output is correct
6 Correct 5 ms 1228 KB Output is correct
7 Correct 6 ms 1228 KB Output is correct
8 Correct 5 ms 1228 KB Output is correct
9 Correct 5 ms 1228 KB Output is correct
10 Correct 5 ms 1228 KB Output is correct
11 Correct 4 ms 1228 KB Output is correct
12 Incorrect 1 ms 716 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -