Submission #787277

#	Time	Username	Problem	Language	Result	Execution time	Memory
787277		pavement	Flood (IOI07_flood)	C++17	100 / 100	128 ms	26604 KiB

flood

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//~ #define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, W, source, ptr1, ptr2, ptr3, ptrq1, ptrq2, ptre, X[100005], Y[100005], A[200005], B[200005], dist[400005], standing[400005], Q[400005];
ii leftmost[200005], upmost[200005], edges[400005];
bitset<400005> vis, up, down, lft, rig;
vector<int> adj2[400005];

int tl(int x) {
	return (x - 1) * 4 + 1;
}

int tr(int x) {
	return (x - 1) * 4 + 2;
}

int bl(int x) {
	return (x - 1) * 4 + 3;
}

int br(int x) {
	return (x - 1) * 4 + 4;
}

namespace ufds {
	int n, lnk[400005], sz[400005];
	
	void init(int n) {
		ufds::n = n;
		for (int i = 1; i <= n; i++) {
			lnk[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x) {
		if (x == lnk[x]) return x;
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (sz[b] > sz[a]) swap(a, b);
		sz[a] += sz[b];
		lnk[b] = a;
	}
};

main() {
	vis.reset();
	up.reset();
	down.reset();
	lft.reset();
	rig.reset();
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i];
	}
	ufds::init(4 * N);
	cin >> W;
	for (int i = 1; i <= W; i++) {
		cin >> A[i] >> B[i];
		if (X[A[i]] == X[B[i]]) {
			leftmost[ptr1++] = mp(X[A[i]], A[i]);
		} else {
			upmost[ptr2++] = mp(Y[A[i]], A[i]);
		}
	}
	sort(leftmost, leftmost + ptr1, greater<ii>());
	sort(upmost, upmost + ptr2);
	for (int i = 1; i <= W; i++) {
		if (X[A[i]] == X[B[i]] && Y[A[i]] > Y[B[i]]) {
			// down
			down[A[i]] = 1;
			up[B[i]] = 1;
			ufds::unite(bl(A[i]), tl(B[i]));
			ufds::unite(br(A[i]), tr(B[i]));
		} else if (X[A[i]] == X[B[i]] && Y[A[i]] < Y[B[i]]) {
			// up
			up[A[i]] = 1;
			down[B[i]] = 1;
			ufds::unite(tl(A[i]), bl(B[i]));
			ufds::unite(tr(A[i]), br(B[i]));
		} else if (Y[A[i]] == Y[B[i]] && X[A[i]] > X[B[i]]) {
			// left
			lft[A[i]] = 1;
			rig[B[i]] = 1;
			ufds::unite(bl(A[i]), br(B[i]));
			ufds::unite(tl(A[i]), tr(B[i]));
		} else if (Y[A[i]] == Y[B[i]] && X[A[i]] < X[B[i]]) {
			// right
			rig[A[i]] = 1;
			lft[B[i]] = 1;
			ufds::unite(br(A[i]), bl(B[i]));
			ufds::unite(tr(A[i]), tl(B[i]));
		} else {
			assert(0);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (!down[i]) {
			ufds::unite(bl(i), br(i));
		}
		if (!up[i]) {
			ufds::unite(tl(i), tr(i));
		}
		if (!lft[i]) {
			ufds::unite(tl(i), bl(i));
		}
		if (!rig[i]) {
			ufds::unite(tr(i), br(i));
		}
	}
	for (int i = 1; i <= N; i++) {
		int utl = ufds::find(tl(i));
		int utr = ufds::find(tr(i));
		int ubl = ufds::find(bl(i));
		int ubr = ufds::find(br(i));
		if (down[i]) {
			if (ubl != ubr) {
				edges[ptre++] = mp(min(ubl, ubr), max(ubl, ubr));
			}
		}
		if (up[i]) {
			if (utl != utr) {
				edges[ptre++] = mp(min(utl, utr), max(utl, utr));
			}
		}
		if (lft[i]) {
			if (utl != ubl) {
				edges[ptre++] = mp(min(utl, ubl), max(utl, ubl));
			}
		}
		if (rig[i]) {
			if (utr != ubr) {
				edges[ptre++] = mp(min(utr, ubr), max(utr, ubr));
			}
		}
	}
	sort(edges, edges + ptre);
	ptre = unique(edges, edges + ptre) - edges;
	for (int i = 0; i < ptre; i++) {
		auto [u, v] = edges[i];
		adj2[u].pb(v);
		adj2[v].pb(u);
	}
	while (ptr1 || ptr2) {
		if (ptr1) {
			source = ufds::find(tl(leftmost[ptr1 - 1].second));
		} else {
			source = ufds::find(tl(upmost[ptr2 - 1].second));
		}
		ptrq1 = ptrq2 = 0;
		Q[ptrq2++] = source;
		vis[source] = 1;
		while (ptrq1 < ptrq2) {
			int u = Q[ptrq1++];
			for (auto v : adj2[u]) {
				if (!vis[v]) {
					vis[v] = 1;
					dist[v] = dist[u] + 1;
					Q[ptrq2++] = v;
				}
			}
		}
		while (ptr1) {
			if (vis[ufds::find(tl(leftmost[ptr1 - 1].second))]) ptr1--;
			else break;
		}
		while (ptr2) {
			if (vis[ufds::find(tl(upmost[ptr2 - 1].second))]) ptr2--;
			else break;
		}
	}
	for (int i = 1; i <= W; i++) {
		if (X[A[i]] == X[B[i]] && Y[A[i]] > Y[B[i]]) {
			// down
			if (dist[ufds::find(bl(A[i]))] == dist[ufds::find(br(A[i]))]) standing[ptr3++] = i;
		} else if (X[A[i]] == X[B[i]] && Y[A[i]] < Y[B[i]]) {
			// up
			if (dist[ufds::find(tl(A[i]))] == dist[ufds::find(tr(A[i]))]) standing[ptr3++] = i;
		} else if (Y[A[i]] == Y[B[i]] && X[A[i]] > X[B[i]]) {
			// left
			if (dist[ufds::find(bl(A[i]))] == dist[ufds::find(tl(A[i]))]) standing[ptr3++] = i;
		} else if (Y[A[i]] == Y[B[i]] && X[A[i]] < X[B[i]]) {
			// right
			if (dist[ufds::find(br(A[i]))] == dist[ufds::find(tr(A[i]))]) standing[ptr3++] = i;
		} else {
			assert(0);
		}
	}
	cout << ptr3 << '\n';
	for (int i = 0; i < ptr3; i++) {
		cout << standing[i] << '\n';
	}
}

Compilation message (stderr)

flood.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main() {
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9