oj.uz

Submission #425739

# Submission time Handle Problem Language Result Execution time Memory
425739 2021-06-13T10:46:28 Z Tangent Toy Train (IOI17_train) C++17
0 / 100
 12 ms 2404 KB 
#include "train.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n = a.size();
	vvii adj(n), radj(n);
	rep(i, u.size()) {
		adj[u[i]].emplace_back(v[i]);
		radj[v[i]].emplace_back(u[i]);
	}

	vii vis(n), stack;
	function<void(int, int)> dfs;
	dfs = [&](int x, int p) {
		vis[x] = true;
		forin(y, adj[x]) {
			if (y != p && !vis[y]) {
				dfs(y, x);
			}
		}
		stack.emplace_back(x);
	};

	rep(i, n) {
		if (!vis[i]) {
			dfs(i, -1);
		}
	}
	
	vii comp(n, -1);
	vvii comps;
	vii hasr;
	function<void(int, int)> dfs2;
	dfs2 = [&](int x, int p) {
		comp[x] = comps.size() - 1;
		comps.back().emplace_back(x);
		if (r[x]) {
			hasr.back() = 1;
		}
		forin(y, radj[x]) {
			if (y != p && comp[y] == -1) {
				dfs2(y, x);
			}
		}
	};
	
	while (!stack.empty()) {
		int x = stack.back();
		stack.pop_back();
		if (comp[x] == -1) {
			comps.emplace_back(vii());
			hasr.emplace_back(0);
			dfs2(x, -1);
		}
	}

	vvii adj3(comps.size());
	rep(i, u.size()) {
		if (comp[u[i]] != comp[v[i]]) {
			adj3[comp[u[i]]].emplace_back(comp[v[i]]);
		}
	}

	vii compseen(comps.size());
	function<void(int, int)> dfs3;
	dfs3 = [&](int x, int p) {
		compseen[x] = 1;
		forin(y, adj3[x]) {
			if (!compseen[y]) {
				dfs3(y, x);
			}
			hasr[x] = max(hasr[x], hasr[y]);
		}
	};
	rep(i, comps.size()) {
		if (!compseen[i]) {
			dfs3(i, -1);
		}
	}

	vii res(n);
	rep(i, n) {
		res[i] = hasr[comp[i]];
	}
	return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1996 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 204 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 10 ms 2404 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 1484 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 12 ms 1612 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 Incorrect 7 ms 1996 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -