oj.uz

답안 #295244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295244 2020-09-09T14:39:32 Z Poimidorka Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 296404 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>


using namespace std;


#define x first
#define y second


typedef long long ll;


const int maxn = 2e6 + 1;


ll func(pair<int, int> a) {
	return ((ll)a.x << 30) | a.y;
}


set<pair<char, int>> rin, rout;
char mat[1001][1001];
vector<int> g[maxn / 2];
vector<int> gr[maxn / 2];
unordered_map<ll, int> num;
int beg[maxn];
int t[maxn * 4];
int pos[maxn];
int a[maxn];
char in[maxn], out[maxn];
bool used[maxn], pus[maxn];
int n, m, uk;


int to(int x, int y) {
	return m * x + y;
}


vector<int> path;


void dfs(int v) {
	pus[v] = 1;
	for (int u : g[v])
		if (!pus[u])
			dfs(u);
	path.push_back(v);
}


void build(int v, int l, int r) {
	if (l == r - 1) {
		t[v] = a[l];
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}


int getmax(int v, int l, int r, int l2, int r2) {
	if (l == l2 && r == r2)
		return t[v];
	int m = (l + r) / 2;
	if (r2 <= m)
		return getmax(v * 2, l, m, l2, r2);
	if (l2 >= m)
		return getmax(v * 2 + 1, m, r, l2, r2);
	return max(getmax(v * 2, l, m, l2, m), getmax(v * 2 + 1, m, r, m, r2));
}


void upd(int v, int l, int r, int pos) {
	if (l == r - 1) {
		t[v] = -1;
		return;
	}
	int m = (l + r) / 2;
	if (pos >= m)
		upd(v * 2 + 1, m, r, pos);
	else
		upd(v * 2, l, m, pos);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}


void de(int v) {
	used[v] = 1;
	for (int u : g[v]) {
		upd(1, 0, uk, num[func({v, u})]);
		if (!used[u]) {
			rin.erase({ in[u], u });
			in[u]--;
			rin.insert({ in[u], u });
		}
	}
	for (int u : gr[v]) {
		upd(1, 0, uk, num[func({u, v})]);
		if (!used[u]) {
			rout.erase({ out[u], u });
			out[u]--;
			rout.insert({ out[u], u });
		}
	}
}


void clr() {
	while (1) {
		if (!rin.empty() && rin.begin()->x == 0) {
			int v = rin.begin()->y;
			rin.erase(rin.begin());
			de(v);
			continue;
		}
		if (!rout.empty() && rout.begin()->x == 0) {
			int v = rout.begin()->y;
			rout.erase(rout.begin());
			de(v);
			continue;
		}
		return;
	}
}


int fn[maxn];


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		g[i].reserve(2);
		gr[i].reserve(2);
		for (int j = 0; j < m; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == '1')
				used[to(i, j)] = 1;
		}
	}
	for (int i = 1; i < n; i++)
		for (int j = 0; j < m; j++)
			if (mat[i][j] != '1' && mat[i - 1][j] != '1') {
				g[to(i - 1, j)].push_back(to(i, j));
				gr[to(i, j)].push_back(to(i - 1, j));
				in[to(i, j)]++;
				out[to(i - 1, j)]++;
			}
	for (int i = 0; i < n; i++)
		for (int j = 1; j < m; j++)
			if (mat[i][j] != '1' && mat[i][j - 1] != '1') {
				g[to(i, j - 1)].push_back(to(i, j));
				gr[to(i, j)].push_back(to(i, j - 1));
				in[to(i, j)]++;
				out[to(i, j - 1)]++;
			}
	used[0] = 1;
	int fn = m * (n - 1) + m - 1;
	used[fn] = 1;
	for (int i = 1; i < fn; i++) {
		if (!used[i]) {
			rin.insert({ in[i], i });
			rout.insert({ out[i], i });
		}
	}
	for (int i = 0; i <= fn; i++)
		if (!pus[i])
			dfs(i);
	reverse(path.begin(), path.end());
	for (int i = 0; i < path.size(); i++)
		pos[path[i]] = i;
	for (int i = 0; i < path.size(); i++) {
		beg[path[i]] = uk;
		for (auto el : g[path[i]]) {
			num[func({path[i], el})] = uk;
			a[uk++] = pos[el];
		}
	}
	build(1, 0, uk);
	clr();
	int q;
	cin >> q;
	/*
	for (auto el : rin)
		cout << '\t' << el.x << ' ' << el.y << endl;
	for (int i = 0; i < path.size(); i++)
		cout << path[i] << ' ';
	cout << endl;
	for (int i = 0; i < uk; i++)
		cout << a[i] << ' ';
	cout << endl;
	*/
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		int p = to(x - 1, y - 1);
		//cout << beg[p] << endl;
		if (!used[p] && getmax(1, 0, uk, 0, beg[p]) <= pos[p]) {
			cout << "0\n";
		}
		else {
			cout << "1\n";
			if (!used[p]) {
				de(p);
				clr();
			}
		}
	}
	return 0;
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:183:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |  for (int i = 0; i < path.size(); i++)
      |                  ~~^~~~~~~~~~~~~
furniture.cpp:185:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |  for (int i = 0; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 49144 KB Output is correct
2 Correct 38 ms 48380 KB Output is correct
3 Correct 48 ms 49408 KB Output is correct
4 Correct 55 ms 49624 KB Output is correct
5 Correct 53 ms 50048 KB Output is correct
6 Correct 60 ms 50356 KB Output is correct
7 Correct 54 ms 50424 KB Output is correct
8 Correct 54 ms 50424 KB Output is correct
9 Correct 54 ms 50424 KB Output is correct

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 49144 KB Output is correct
2 Correct 38 ms 48380 KB Output is correct
3 Correct 48 ms 49408 KB Output is correct
4 Correct 55 ms 49624 KB Output is correct
5 Correct 53 ms 50048 KB Output is correct
6 Correct 60 ms 50356 KB Output is correct
7 Correct 54 ms 50424 KB Output is correct
8 Correct 54 ms 50424 KB Output is correct
9 Correct 54 ms 50424 KB Output is correct
10 Correct 162 ms 60988 KB Output is correct
11 Correct 54 ms 50316 KB Output is correct
12 Correct 4551 ms 294800 KB Output is correct
13 Correct 1890 ms 262948 KB Output is correct
14 Correct 4444 ms 291780 KB Output is correct
15 Execution timed out 5078 ms 296404 KB Time limit exceeded
16 Halted 0 ms 0 KB -