oj.uz

답안 #249275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249275 2020-07-14T14:48:47 Z kostia244 장난감 기차 (IOI17_train) C++17
27 / 100
 2000 ms 102344 KB 
#include "train.h"
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,sse,sse2,avx2,ssse3,tune=native")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5050;
int n, m, loop[maxn];
vector<int> g[maxn], a, r, res;
namespace s1 {
	bool dfs(int v) {
		if(a[v] && loop[v] && r[v]) return true;
		if(!a[v] && loop[v] && !r[v]) return false;
		if(g[v].size()) return dfs(v+1);
		return !a[v];
	}
};
void solve1() {
	using namespace s1;
	for(int i = 0; i < n; i++) res.push_back(dfs(i));
}
namespace brt {
};
void solvebrt() {
	using namespace brt;
	
}
namespace s3 {
	int s[maxn], dp[maxn][maxn], F;
	void dfs(int v, int p) {
		if(!F && r[v]) return;
		if(dp[p][v]) return;
		dp[p][v] = 1;
		for(int i : g[v])
			dfs(i, p);
	}
};
void solvef(int f) {
	using namespace s3;
	F = f;
	memset(dp, 0, sizeof dp);
	for(int i = 0; i < n; i++) dfs(i, i);
	for(int i = 0; i < n; i++) {
		dp[i][i] = loop[i] && (f || !r[i]);
		for(int j = 0; j < n; j++) {
			s[i] |= dp[i][j]&&dp[j][i] && (!f || (r[j]||r[j]));
		}
	}
	if(!f) {
		F = 1;
		memset(dp, 0, sizeof dp);
		for(int i = 0; i < n; i++) dfs(i, i);
	}
	for(int i = 0; i < n; i++) {
		int v = s[i];
		for(int j = 0; j < n; j++) {
			v |= dp[i][j] && s[j];
		}
		res.push_back(v^(!f));
	}
}
std::vector<int> who_wins(std::vector<int> _a, std::vector<int> _r, std::vector<int> u, std::vector<int> v) {
	n = _a.size();
	m = u.size();
	a = _a, r = _r;
	int ss1 = 1;
	set<array<int, 2>> pr;
	for(int i = 0; i < m; i++) {
		if(!pr.insert({u[i], v[i]}).second) continue;
		if(u[i] != v[i])
			g[u[i]].push_back(v[i]);
		else loop[u[i]] = 1;
		ss1 &= u[i] == v[i] || v[i] == u[i]+1;
	}
	if(ss1) solve1();
	//else if(n < 16) solvebrt();
	else solvef(count(a.begin(), a.end(), 1) == n);
	return res;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1152 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 7 ms 1244 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 7 ms 1152 KB Output is correct
10 Correct 6 ms 1152 KB Output is correct
11 Correct 5 ms 896 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 100220 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 554 ms 102264 KB Output is correct
2 Correct 540 ms 102224 KB Output is correct
3 Correct 533 ms 102072 KB Output is correct
4 Correct 1528 ms 102264 KB Output is correct
5 Correct 1204 ms 102008 KB Output is correct
6 Correct 943 ms 102008 KB Output is correct
7 Correct 799 ms 102008 KB Output is correct
8 Correct 638 ms 102136 KB Output is correct
9 Correct 632 ms 101880 KB Output is correct
10 Correct 731 ms 101816 KB Output is correct
11 Correct 612 ms 101880 KB Output is correct
12 Correct 153 ms 101880 KB Output is correct
13 Correct 1581 ms 102344 KB Output is correct
14 Correct 1571 ms 102264 KB Output is correct
15 Correct 1586 ms 102264 KB Output is correct
16 Correct 1597 ms 102264 KB Output is correct
17 Correct 1597 ms 102268 KB Output is correct
18 Correct 637 ms 101624 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1059 ms 101624 KB Output is correct
2 Correct 499 ms 101752 KB Output is correct
3 Correct 742 ms 101880 KB Output is correct
4 Correct 726 ms 102012 KB Output is correct
5 Correct 1124 ms 102028 KB Output is correct
6 Correct 956 ms 101880 KB Output is correct
7 Correct 936 ms 101880 KB Output is correct
8 Correct 704 ms 101788 KB Output is correct
9 Correct 161 ms 101752 KB Output is correct
10 Correct 1369 ms 102008 KB Output is correct
11 Correct 1350 ms 102140 KB Output is correct
12 Correct 1351 ms 102136 KB Output is correct
13 Correct 1489 ms 102008 KB Output is correct
14 Correct 910 ms 101888 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2056 ms 102008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1152 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 7 ms 1244 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 7 ms 1152 KB Output is correct
10 Correct 6 ms 1152 KB Output is correct
11 Correct 5 ms 896 KB Output is correct
12 Incorrect 60 ms 100220 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -