oj.uz

Submission #409537

# Submission time Handle Problem Language Result Execution time Memory
409537 2021-05-21T04:10:19 Z Kevin_Zhang_TW Toy Train (IOI17_train) C++17
0 / 100
 8 ms 1828 KB 
#include <bits/stdc++.h>
#include "train.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto l, auto r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 5005;

int n;
vector<int> edge[MAX_N], rev_edge[MAX_N];
vector<pair<int,int>> alle;
bool rm[MAX_N], is_a[MAX_N], vis[MAX_N];

int out_deg[MAX_N];

void dfs1(int x) {
	if (rm[x] || vis[x]) return;
	vis[x] = true;
	for (int u : rev_edge[x]) {
		if (is_a[u] || --out_deg[u] == 0)
			dfs1(u);
	}
}

void dfs2(int x) {
	if (rm[x] || vis[x]) return;
	vis[x] = true;
	for (int u : rev_edge[x]) {
		if (!is_a[u] || --out_deg[u] == 0)
			dfs2(u);
	}
}

void init_g() {
	fill(out_deg, out_deg + n, 0);
	fill(vis, vis + n, false);
	for (auto [a, b] : alle) {
		if (rm[a] || rm[b]) continue;
		++out_deg[a];
	}
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	n = a.size();
	for (int i = 0;i < u.size();++i) {
		alle.pb(v[i], u[i]);
		rev_edge[v[i]].pb(u[i]);
	}
	vector<int> res(n);

	for (int i = 0;i < n;++i)
		is_a[i] = a[i];

	int node_cnt = n;
	while (node_cnt) {
		init_g();
		for (int i = 0;i < n;++i) if (!rm[i]) {
			if (r[i] == 1) dfs1(i);
		}
		if (count(vis, vis + n, true) == node_cnt) {
			for (int i = 0;i < n;++i)
				if (!rm[i]) res[i] = 1;
			break;
		}
		vector<int> bwin;
		for (int i = 0;i < n;++i) if (!rm[i]) {
			if (!vis[i]) bwin.pb(i);
		}
		init_g();
		for (int i : bwin) dfs2(i);
		for (int i = 0;i < n;++i) if (!rm[i]) {
			if (vis[i] == true) {
				rm[i] = true;
				--node_cnt;
			}
		}
	}

	return res;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0;i < u.size();++i) {
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 972 KB 3rd lines differ - on the 50th token, expected: '1', found: '0'
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 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 8 ms 1828 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 7 ms 1440 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1576 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 Incorrect 6 ms 972 KB 3rd lines differ - on the 50th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -