oj.uz

Submission #406901

# Submission time Handle Problem Language Result Execution time Memory
406901 2021-05-18T07:44:53 Z cheissmart Toy Train (IOI17_train) C++14
16 / 100
 1288 ms 1808 KB 
#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]);
	}
	if(count(ALL(a), 0)) {
		vi dp(n);
		for(int i = n - 1; i >= 0; i--) {
			bool has_nxt = count(ALL(G[i]), i + 1);
			bool has_loop = count(ALL(G[i]), i);
			if(has_nxt == 0) {
				dp[i] = r[i];
			} else {
				if(has_loop && a[i] == r[i]) dp[i] = a[i];
				else dp[i] = dp[i + 1];
			}
		}
		return dp;
	}

	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 972 KB Output is correct
2 Correct 5 ms 1136 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 5 ms 1148 KB Output is correct
5 Correct 6 ms 1076 KB Output is correct
6 Correct 5 ms 1088 KB Output is correct
7 Correct 5 ms 1100 KB Output is correct
8 Correct 10 ms 1228 KB Output is correct
9 Correct 5 ms 1100 KB Output is correct
10 Correct 5 ms 1100 KB Output is correct
11 Correct 4 ms 1100 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB 3rd lines differ - on the 1st 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 247 ms 1808 KB Output is correct
2 Correct 240 ms 1740 KB Output is correct
3 Correct 224 ms 1740 KB Output is correct
4 Correct 1245 ms 1732 KB Output is correct
5 Correct 977 ms 1600 KB Output is correct
6 Correct 653 ms 1500 KB Output is correct
7 Correct 547 ms 1592 KB Output is correct
8 Correct 360 ms 1484 KB Output is correct
9 Correct 316 ms 1484 KB Output is correct
10 Correct 423 ms 1436 KB Output is correct
11 Correct 364 ms 1420 KB Output is correct
12 Correct 36 ms 1408 KB Output is correct
13 Correct 1261 ms 1732 KB Output is correct
14 Correct 1261 ms 1728 KB Output is correct
15 Correct 1261 ms 1668 KB Output is correct
16 Correct 1270 ms 1784 KB Output is correct
17 Correct 1288 ms 1664 KB Output is correct
18 Correct 459 ms 1472 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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