oj.uz

답안 #295235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295235 2020-09-09T14:35:56 Z Poimidorka Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 329372 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


const int maxn = 2e6 + 1;


set<pair<char, int>> rin, rout;
char mat[1001][1001];
vector<int> g[maxn / 2];
vector<int> gr[maxn / 2];
map<pair<int, int>, 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[{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[{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;
	}
}


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[{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:172:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |  for (int i = 0; i < path.size(); i++)
      |                  ~~^~~~~~~~~~~~~
furniture.cpp:174:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |  for (int i = 0; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 49400 KB Output is correct
2 Correct 47 ms 48512 KB Output is correct
3 Correct 59 ms 49784 KB Output is correct
4 Correct 56 ms 50040 KB Output is correct
5 Correct 58 ms 50172 KB Output is correct
6 Correct 67 ms 50808 KB Output is correct
7 Correct 76 ms 51064 KB Output is correct
8 Correct 60 ms 50784 KB Output is correct
9 Correct 60 ms 50808 KB Output is correct

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 49400 KB Output is correct
2 Correct 47 ms 48512 KB Output is correct
3 Correct 59 ms 49784 KB Output is correct
4 Correct 56 ms 50040 KB Output is correct
5 Correct 58 ms 50172 KB Output is correct
6 Correct 67 ms 50808 KB Output is correct
7 Correct 76 ms 51064 KB Output is correct
8 Correct 60 ms 50784 KB Output is correct
9 Correct 60 ms 50808 KB Output is correct
10 Correct 199 ms 62712 KB Output is correct
11 Correct 61 ms 50560 KB Output is correct
12 Execution timed out 5042 ms 329372 KB Time limit exceeded
13 Halted 0 ms 0 KB -