oj.uz

답안 #295266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295266 2020-09-09T14:50:15 Z Poimidorka Furniture (JOI20_furniture) C++14
100 / 100
 2993 ms 245944 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;
}

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;
int susp[maxn * 3];
int head = 0, tail = 0;


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]) {
			in[u]--;
			if (in[u] == 0)
				susp[tail++] = u;
		}
	}
	for (int u : gr[v]) {
		upd(1, 0, uk, num[func({u, v})]);
		if (!used[u]) {
			out[u]--;
			if (out[u] == 0)
				susp[tail++] = u;
		}
	}
}


void clr() {
	while (head != tail) {
		if (!used[susp[head]])
			de(susp[head++]);
		else
			head++;
	}
}

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 ((in[i] == 0 || out[i] == 0)) {
			susp[tail++] = 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]) {
				susp[tail++] = p;
				clr();
			}
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 48640 KB Output is correct
2 Correct 37 ms 48128 KB Output is correct
3 Correct 41 ms 48760 KB Output is correct
4 Correct 44 ms 49016 KB Output is correct
5 Correct 45 ms 49272 KB Output is correct
6 Correct 54 ms 49656 KB Output is correct
7 Correct 47 ms 49656 KB Output is correct
8 Correct 48 ms 49656 KB Output is correct
9 Correct 48 ms 49656 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 48640 KB Output is correct
2 Correct 37 ms 48128 KB Output is correct
3 Correct 41 ms 48760 KB Output is correct
4 Correct 44 ms 49016 KB Output is correct
5 Correct 45 ms 49272 KB Output is correct
6 Correct 54 ms 49656 KB Output is correct
7 Correct 47 ms 49656 KB Output is correct
8 Correct 48 ms 49656 KB Output is correct
9 Correct 48 ms 49656 KB Output is correct
10 Correct 121 ms 56984 KB Output is correct
11 Correct 47 ms 49408 KB Output is correct
12 Correct 2350 ms 215364 KB Output is correct
13 Correct 1274 ms 191320 KB Output is correct
14 Correct 2534 ms 209064 KB Output is correct
15 Correct 2672 ms 212728 KB Output is correct
16 Correct 2573 ms 232276 KB Output is correct
17 Correct 2890 ms 240504 KB Output is correct
18 Correct 2993 ms 236624 KB Output is correct
19 Correct 2745 ms 245944 KB Output is correct
20 Correct 2863 ms 245804 KB Output is correct
21 Correct 2744 ms 245800 KB Output is correct