Submission #406899

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
406899	2021-05-18T07:43:09 Z	cheissmart	Toy Train (IOI17_train)	C++14	11 / 100	1331 ms	1980 KB

train

#include "train.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 5005;

vi G[N], rG[N], order, r;
int vis[N], scc[N], cnt[N], good[N], tt;

void dfs(int u) {
	vis[u] = 1;
	for(int v:rG[u]) if(!vis[v]) dfs(v);
	order.PB(u);
}

void dfs1(int u, int id) {
	scc[u] = id;
	cnt[id]++;
	if(r[u]) good[id] = 1;
	for(int v:G[u]) if(scc[v] == 0) dfs1(v, id);
}

vi who_wins(vi a, vi r, vi u, vi v) {
	::r = r;
	int n = a.size(), m = u.size();
	assert(u.size() == v.size());

	for(int i = 0; i < m; i++) {
		G[u[i]].PB(v[i]);
		rG[v[i]].PB(u[i]);
	}
	for(int i = 0; i < n; i++) if(!vis[i])
		dfs(i);
	reverse(ALL(order));
	for(int i:order) if(!scc[i]) {
		dfs1(i, ++tt);
	}
	vi ans(n);
	for(int i = 0; i < n; i++) {
		vi vis(n);
		function<void(int)> dfs = [&] (int u) {
			vis[u] = 1;
			int id = scc[u];
			if(good[id]) {
				if(cnt[id] > 1) ans[i] = 1;
				else if(count(ALL(G[u]), u)) ans[i] = 1;
			}
			for(int v:G[u]) if(!vis[v]) dfs(v);
		};
		dfs(i);
	}
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	214 ms	1820 KB	Output is correct
2	Correct	234 ms	1980 KB	Output is correct
3	Correct	246 ms	1956 KB	Output is correct
4	Correct	1231 ms	1860 KB	Output is correct
5	Correct	932 ms	1860 KB	Output is correct
6	Correct	642 ms	1732 KB	Output is correct
7	Correct	546 ms	1676 KB	Output is correct
8	Correct	348 ms	1612 KB	Output is correct
9	Correct	334 ms	1668 KB	Output is correct
10	Correct	457 ms	1636 KB	Output is correct
11	Correct	373 ms	1612 KB	Output is correct
12	Correct	36 ms	1592 KB	Output is correct
13	Correct	1261 ms	1884 KB	Output is correct
14	Correct	1308 ms	1872 KB	Output is correct
15	Correct	1331 ms	1872 KB	Output is correct
16	Correct	1271 ms	1868 KB	Output is correct
17	Correct	1295 ms	1868 KB	Output is correct
18	Correct	430 ms	1484 KB	Output is correct