oj.uz

Submission #439453

# Submission time Handle Problem Language Result Execution time Memory
439453 2021-06-30T03:30:07 Z flappybird Toy Train (IOI17_train) C++14
16 / 100
 1608 ms 1860 KB 
#include "train.h"

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef int ll;

#define MAX 6000

vector<ll> A, s;
ll N, M;
vector<ll> adj[MAX], rev[MAX], deg, d;
ll mp[MAX][MAX];

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	ll i;
	A = a;
	N = a.size();
	M = u.size();
	d.resize(N);
	deg.resize(N);
	vector<ll> res, ans;
	res.resize(N);
	ans.resize(N);
	for (i = 0; i < N; i++) if (r[i]) s.push_back(i);
	for (i = 0; i < M; i++) adj[u[i]].push_back(v[i]), rev[v[i]].push_back(u[i]);
	ll T;
	for (T = 1; T <= N; T++) {
		for (i = 0; i < N; i++) {
			for (auto x : adj[i]) {
				if (ans[x]) continue;
				d[i]++;
			}
		}
		deg = d;
		queue<ll> q;
		for (auto st : s) {
			if (ans[st]) continue;
			q.push(st);
			res[st] = 1;
		}
		ll j;
		while (!q.empty()) {
			ll t = q.front();
			q.pop();
			for (auto x : rev[t]) {
				if (ans[x]) continue;
				if (res[x]) continue;
				deg[x]--;
				if (a[x]) q.push(x), res[x] = 1;
				else if (deg[x] <= 0) q.push(x), res[x] = 1;
			}
		}
		//impossible
		vector<ll> imp;
		for (i = 0; i < N; i++) if (!res[i]) imp.push_back(i);
		while (!q.empty()) q.pop();
		for (auto st : imp) {
			if (ans[st]) continue;
			q.push(st);
			ans[st] = 1;
		}
		while (!q.empty()) {
			ll t = q.front();
			q.pop();
			for (auto x : rev[t]) {
				if (ans[x]) continue;
				deg[x]--;
				if (!a[x]) q.push(x), ans[x] = 1;
				else if (deg[x] <= 0) q.push(x), ans[x] = 1;
			}
		}
	}
	for (i = 0; i < N; i++) ans[i] = !ans[i];
	return ans;
}

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:46:6: warning: unused variable 'j' [-Wunused-variable]
   46 |   ll j;
      |      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 1288 KB Output is correct
2 Correct 542 ms 1268 KB Output is correct
3 Correct 512 ms 1228 KB Output is correct
4 Correct 485 ms 1348 KB Output is correct
5 Correct 518 ms 1268 KB Output is correct
6 Correct 538 ms 1256 KB Output is correct
7 Correct 411 ms 1264 KB Output is correct
8 Correct 525 ms 1260 KB Output is correct
9 Correct 570 ms 1348 KB Output is correct
10 Correct 643 ms 1232 KB Output is correct
11 Correct 630 ms 1244 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 1 ms 588 KB 3rd lines differ - on the 3rd token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 1736 KB Output is correct
2 Correct 395 ms 1860 KB Output is correct
3 Correct 369 ms 1740 KB Output is correct
4 Correct 932 ms 1732 KB Output is correct
5 Correct 1000 ms 1732 KB Output is correct
6 Incorrect 598 ms 1732 KB 3rd lines differ - on the 12th token, expected: '0', found: '1'
7 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1175 ms 1512 KB Output is correct
2 Correct 767 ms 1568 KB Output is correct
3 Correct 654 ms 1728 KB Output is correct
4 Correct 614 ms 1612 KB Output is correct
5 Correct 1033 ms 1708 KB Output is correct
6 Correct 857 ms 1668 KB Output is correct
7 Correct 983 ms 1680 KB Output is correct
8 Correct 643 ms 1732 KB Output is correct
9 Correct 1608 ms 1740 KB Output is correct
10 Correct 1150 ms 1740 KB Output is correct
11 Correct 1251 ms 1732 KB Output is correct
12 Correct 1148 ms 1740 KB Output is correct
13 Correct 969 ms 1732 KB Output is correct
14 Correct 859 ms 1732 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 1288 KB Output is correct
2 Correct 542 ms 1268 KB Output is correct
3 Correct 512 ms 1228 KB Output is correct
4 Correct 485 ms 1348 KB Output is correct
5 Correct 518 ms 1268 KB Output is correct
6 Correct 538 ms 1256 KB Output is correct
7 Correct 411 ms 1264 KB Output is correct
8 Correct 525 ms 1260 KB Output is correct
9 Correct 570 ms 1348 KB Output is correct
10 Correct 643 ms 1232 KB Output is correct
11 Correct 630 ms 1244 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 584 KB Output is correct
15 Incorrect 1 ms 588 KB 3rd lines differ - on the 3rd token, expected: '1', found: '0'
16 Halted 0 ms 0 KB -