oj.uz

Submission #587395

# Submission time Handle Problem Language Result Execution time Memory
587395 2022-07-01T18:59:22 Z GusterGoose27 Flood (IOI07_flood) C++11
73 / 100
 83 ms 27716 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MAXW = 2e5;
int uf[MAXW]; // for vertical lines, left is +0, right is +w. For horizontal, bottom is +0, top is +w
set<pii> active_points;
int point_mask[MAXN]; // right, up, left, down
pii points[MAXN];
int windex[MAXN][4];
int n, w;
vector<int> edges[2*MAXW];
pii walls[MAXW];
vector<pii> w_edges[MAXN];
bool deact[MAXW];
vector<int> standing;
int deg[MAXN];
int dist[2*MAXW];

int find(int i) {
	return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}

void mask_add(int cur, int other, int w) {
	if (points[other].first > points[cur].first) {
		point_mask[cur] += 1;
		windex[cur][0] = w;
	}
	if (points[other].second > points[cur].second) {
		point_mask[cur] += 2;
		windex[cur][1] = w;
	}
	if (points[other].first < points[cur].first) {
		point_mask[cur] += 4;
		windex[cur][2] = w;
	}
	if (points[other].second < points[cur].second) {
		point_mask[cur] += 8;
		windex[cur][3] = w;
	}
}

int shift(int mask, int s) {
	int rshift = mask >> s;
	int lshift = mask % (1 << s);
	return (lshift << (4-s)) + rshift;
}

int get_cc(int i, int bit) {
	int base = windex[i][bit];
	if (bit == 1 || bit == 2) return base;
	return base+w;
}

int get_cw(int i, int bit) {
	return (get_cc(i, bit)+w)%(2*w);
}

void prune(int cur) {
	deg[cur] = 0;
	for (pii next: w_edges[cur]) {
		if (deact[next.second]) continue;
		deact[next.second] = 1;
		deg[next.first]--;
		if (deg[next.first] == 1) prune(next.first);
	}
}

void bfs(int s) {
	dist[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int next: edges[cur]) {
			if (dist[next] != -1) continue;
			dist[next] = dist[cur]+1;
			q.push(next);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		points[i] = pii(x, y);
	}
	cin >> w;
	fill(uf, uf+2*w, -1);
	for (int i = 0; i < w; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		walls[i] = pii(x, y);
		w_edges[x].push_back(pii(y, i));
		w_edges[y].push_back(pii(x, i));
		deg[x]++;
		deg[y]++;
	}
	for (int i = 0; i < n; i++)
		if (deg[i] == 1) prune(i);
	for (int i = 0; i < w; i++) {
		if (deact[i]) {
			standing.push_back(i);
			continue;
		}
		int x = walls[i].first;
		int y = walls[i].second;
		active_points.insert(pii(points[x].first, x));
		active_points.insert(pii(points[y].first, y));
		mask_add(x, y, i);
		mask_add(y, x, i);
	}
	for (pii p: active_points) {
		int i = p.second;
		for (int bit = 0; bit < 4; bit++) {
			if ((point_mask[i] & (1 << bit)) == 0) continue;
			int ccval = get_cc(i, bit);
			int maskcpy = shift(point_mask[i], bit+1); // shift to the right
			int nbit = log2(maskcpy&(-maskcpy));
			nbit = (nbit+bit+1)%4;
			int cwval = get_cw(i, nbit);
			int ida = find(ccval);
			int idb = find(cwval);
			if (ida != idb) uf[ida] = idb;
		}
	}
	for (int i = 0; i < w; i++) {
		if (deact[i]) continue;
		int a = find(i);
		int b = find(w+i);
		//assert(a != b); // wouldve been deactivated
		if (a == b) continue;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	fill(dist, dist+2*w, -1);
	for (pii p: active_points) {
		int i = p.second;
		int bit = log2(point_mask[i] & (-point_mask[i]));
		if (dist[find(get_cc(i, bit))] != -1) continue;
		assert((point_mask[i] & 2) || (point_mask[i] & 8));
		if (point_mask[i] & 2) {
			int out = get_cc(i, 1);
			bfs(find(out));
		}
		else {
			int out = get_cw(i, 3);
			bfs(find(out));
		}
	}
	for (int i = 0; i < w; i++) {
		if (deact[i]) continue;
		int a = find(i);
		int b = find(w+i);
		if (dist[a] == dist[b]) standing.push_back(i);
	}
	cout << standing.size() << '\n';
	for (int i: standing) cout << (i+1) << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12100 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 9 ms 12104 KB Output is correct
3 Correct 6 ms 12096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12116 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12152 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 7 ms 12112 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15392 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 24936 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 27716 KB Output is correct
2 Runtime error 35 ms 27212 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 27204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 27212 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -