Submission #249246

#	Time	Username	Problem	Language	Result	Execution time	Memory
249246		kostia244	장난감 기차 (IOI17_train)	C++17	5 / 100	2107 ms	202220 KiB

train

#include "train.h"
#pragma GCC optimze("O2")
#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][2];
	void dfs(int v, int p, int s) {
		if(dp[p][v][s]) return;
		dp[p][v][s] = 1;
		for(int i : g[v])
			dfs(i, p, s|r[i]);
	}
	bool check(int i, int f) {
		if(s[i] != -1) return s[i];
		s[i] = dp[i][i][1];
		for(int j : g[i]) s[i] |= check(j, f);
		return s[i];
	}
};
void solvef(int f) {
	using namespace s3;
	memset(dp, 0, sizeof dp);
	memset(s, -1, sizeof s);
	for(int i = 0; i < n; i++) if(loop[i]) dfs(i, i, r[i]);
	for(int i = 0; i < n; i++)
		for(int j : g[i])
			dfs(j, i, r[i]|r[j]);//, cout << j << " " << i << " " << (r[i]|r[j]) << ";;\n";
	for(int i = 0; i < n; i++)
		res.push_back(check(i, 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;
}

Compilation message (stderr)

train.cpp:2:0: warning: ignoring #pragma GCC optimze [-Wunknown-pragmas]
 #pragma GCC optimze("O2")

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51