oj.uz

Submission #813782

# Submission time Handle Problem Language Result Execution time Memory
813782 2023-08-08T03:40:56 Z ono_de206 L-triominoes (CEOI21_ltriominoes) C++14
11 / 100
 8000 ms 724 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
 
// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
 
template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
	return out;
}
 
template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
	return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
	return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 1 << 14;
vector<int> g[mxn];
map<int, int> gg;
int n, m, k, S;

bool is(int x, int bit) {
	return (x & (1 << bit)) > 0;
}

void build(int now, int ans, int bit) {
	if(bit - 2 >= 0 && !is(now, bit - 2)) return;
	if(bit == n) {
		if(now == (1 << n) - 1) g[S].pb(ans);
		return;
	}
	// 1 **
	//    *
	if(bit - 1 >= 0 && !is(now, bit) && !is(ans, bit) && !is(ans, bit - 1)) {
		build(now ^ (1 << bit), ans ^ (1 << bit) ^ (1 << (bit - 1)), bit + 1);
	}
	// 2 **
	//   *
	if(bit + 1 < n && !is(now, bit) && !is(ans, bit) && !is(ans, bit + 1)) {
		build(now ^ (1 << bit), ans ^ (1 << bit) ^ (1 << (bit + 1)), bit + 1);
	}
	// 3 *
	//   **
	if(bit - 1 >= 0 && !is(now, bit - 1) && !is(now, bit) && !is(ans, bit - 1)) {
		build(now ^ (1 << bit) ^ (1 << (bit - 1)), ans ^ (1 << (bit - 1)), bit + 1);
	}
	// 4  *
	//   **
	if(bit - 1 >= 0 && !is(now, bit - 1) && !is(now, bit) && !is(ans, bit)) {
		build(now ^ (1 << bit) ^ (1 << (bit - 1)), ans ^ (1 << bit), bit + 1);
	}
	// 5
	build(now, ans, bit + 1);
}

vector<vector<int>> get(vector<vector<int>> &a, vector<vector<int>> &b) {
	vector<vector<int>> ret(1 << n, vector<int>(1 << n));
	for(int k = 0; k < (1 << n); k++) {
		for(int i = 0; i < (1 << n); i++) {
			for(int j = 0; j < (1 << n); j++) {
				if(a[i][k] && b[k][j]) ret[i][j] = 1;
			}
		}
	}
	return ret;
}
 
vector<int> solve(vector<int> &prdp, int len, int pp) {
	vector<vector<int>> can(1 << n, vector<int>(1 << n)), tmp(1 << n, vector<int>(1 << n));
	for(int i = 0; i < (1 << n); i++) {
		for(int x : g[i]) {
			tmp[i][x] = 1;
		}
	} 
	for(int i = 0; i < (1 << n); i++) {
		can[i][i] = 1;
	}
	for(; len; len >>= 1) {
		if(len & 1) can = get(can, tmp);
		tmp = get(tmp, tmp);
	}
	vector<int> ret(1 << n);
	for(int i = 0; i < (1 << n); i++) {
		if(!prdp[i]) continue;
		for(int j = 0; j < (1 << n); j++) {
			if(j & pp) continue;
			if(can[i][j]) ret[j | pp] = 1;
		}
	}
	return ret;
}

void go() {
	cin >> n >> m >> k;
	for(int i = 0; i < k; i++) {
		int x, y; cin >> x >> y;
		gg[y] |= (1 << (x - 1));
	}
	for(int i = 0; i < (1 << n); i++) {
		S = i;
		build(i, 0, 0);
		sort(all(g[S]));
		g[S].erase(unique(all(g[S])), g[S].end());
	}
	int ls = 0;
	vector<int> dp(1 << n);
	dp[(1 << n) - 1] = 1;
	gg[m + 1] = (1 << n) - 1;
	if(n <= 3) {
		for(auto it : gg) {
			dp = solve(dp, it.ff - ls, it.ss);
			ls = it.ff;
		}
		if(dp[(1 << n) - 1]) cout << "YES\n";
		else cout << "NO\n";
		return;
	}
	for(auto it : gg) {
		int dis = it.ff - ls;
		// int kk = (dis - 2) / 6;
		// if(kk >= 0) dis -= kk * 6;
		for(int t = 1; t <= dis; t++) {
			vector<int> nwdp(1 << n);
			for(int i = 0; i < (1 << n); i++) {
				if(!dp[i]) continue;
				for(int x : g[i]) {
					if(t == dis && (i & it.ss) > 0) continue;
					if(t == dis) nwdp[x | it.ss] = 1;
					else nwdp[x] = 1;
				}
			}
			swap(dp, nwdp);
		}
		ls = it.ff;
	}
	if(dp[(1 << n) - 1]) cout << "YES\n";
	else cout << "NO\n";
}

signed main() {
	// #ifndef ONO
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8029 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 6 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 6 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 0 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 3 ms 724 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 9 ms 716 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 7 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 2 ms 596 KB Output is correct
38 Correct 2 ms 596 KB Output is correct
39 Correct 2 ms 596 KB Output is correct
40 Correct 6 ms 720 KB Output is correct
41 Correct 4 ms 596 KB Output is correct
42 Correct 1 ms 596 KB Output is correct
43 Correct 3 ms 596 KB Output is correct
44 Correct 1 ms 724 KB Output is correct
45 Correct 3 ms 724 KB Output is correct
46 Correct 1 ms 596 KB Output is correct
47 Correct 3 ms 596 KB Output is correct
48 Correct 2 ms 596 KB Output is correct
49 Correct 1 ms 596 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 716 KB Output is correct
2 Incorrect 738 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8061 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -