oj.uz

Submission #58636

# Submission time Handle Problem Language Result Execution time Memory
58636 2018-07-18T14:27:10 Z reality Toy Train (IOI17_train) C++17
0 / 100
 45 ms 25312 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
#include "train.h"

vi answer;
int n;
const int N = 1e6;
vi G[N];
int deg[N];
int d[N];
vi who;

void dfs(int node) {
	for (auto it : G[node]) {
		--deg[it];
		if (!deg[it] && who[it])
			dfs(it);
	}
}

vi who_wins(vi a, vi b, vi u, vi v) {
	n = a.size();
	for (auto & it : b)
		it ^= 1;
	who = b;
	for (int i = 0;i < u.size();++i)
		G[v[i]].pb(u[i]),++d[u[i]];
	answer.resize(n);
	for (int i = 0;i < n;++i)
		answer[i] = 1;
	int ok;
	do {
		ok = 0;
		who = b;
		for (int i = 0;i < n;++i)
			deg[i] = a[i] ? 1 : d[i];
		for (int i = 0;i < n;++i)
			if (!who[i])
				dfs(i);
		for (int i = 0;i < n;++i) {
			if (b[i] && answer[i] && deg[i] > 0)
				ok = 1;
			answer[i] &= deg[i] <= 0;
		}
	} while (ok);
	return answer;
}

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:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < u.size();++i)
                 ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 25036 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 45 ms 25036 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 Correct 39 ms 25220 KB Output is correct
2 Correct 39 ms 25268 KB Output is correct
3 Correct 37 ms 25284 KB Output is correct
4 Correct 42 ms 25312 KB Output is correct
5 Correct 31 ms 25312 KB Output is correct
6 Correct 30 ms 25312 KB Output is correct
7 Correct 33 ms 25312 KB Output is correct
8 Incorrect 40 ms 25312 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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