Submission #787271

#	Time	Username	Problem	Language	Result	Execution time	Memory
787271		pavement	Flood (IOI07_flood)	C++17	64 / 100	928 ms	65536 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, X[100005], Y[100005], A[200005], B[200005], dist[400005];
bool vis[400005];
vector<int> standing;
map<ii, int> seen;
vector<int> adj[400005], adj2[400005];
queue<int> Q;
set<ii> leftmost, upmost, edges;

int conv(int r, int c) {
	if (seen.find(mp(r, c)) != seen.end()) return seen[mp(r, c)];
	assert((int)seen.size() + 1 <= 4 * N);
	return seen[mp(r, c)] = seen.size() + 1;
}

int tl(int x) {
	return conv(X[x] - 1, Y[x]);
}

int tr(int x) {
	return conv(X[x], Y[x]);
}

int bl(int x) {
	return conv(X[x] - 1, Y[x] - 1);
}

int br(int x) {
	return conv(X[x], Y[x] - 1);
}

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) {
		assert(1 <= x && x <= n);
		if (x == lnk[x]) return x;
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		assert(1 <= a && a <= n && 1 <= b && b <= n);
		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() {
	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];
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
		if (X[A[i]] == X[B[i]]) {
			leftmost.emplace(X[A[i]], A[i]);
		} else {
			upmost.emplace(Y[A[i]], A[i]);
		}
	}
	for (int i = 1; i <= N; i++) {
		bool down = 0, up = 0, left = 0, right = 0;
		for (int j : adj[i]) {
			if (X[i] == X[j] && Y[i] > Y[j]) {
				// i --> j goes down
				down = 1;
				ufds::unite(bl(i), tl(j));
			} else if (X[i] == X[j] && Y[i] < Y[j]) {
				// i --> j goes up
				up = 1;
				ufds::unite(tr(i), br(j));
			} else if (Y[i] == Y[j] && X[i] > X[j]) {
				// i --> j goes left
				left = 1;
				ufds::unite(tl(i), tr(j));
			} else if (Y[i] == Y[j] && X[i] < X[j]) {
				// i --> j goes right
				right = 1;
				ufds::unite(br(i), bl(j));
			} else {
				assert(0);
			}
		}
		if (!down) {
			ufds::unite(bl(i), br(i));
		}
		if (!up) {
			ufds::unite(tl(i), tr(i));
		}
		if (!left) {
			ufds::unite(tl(i), bl(i));
		}
		if (!right) {
			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));
		for (int j : adj[i]) {
			if (X[i] == X[j] && Y[i] > Y[j]) {
				// i --> j goes down
				if (ubl != ubr) {
					edges.emplace(min(ubl, ubr), max(ubl, ubr));
				}
			} else if (X[i] == X[j] && Y[i] < Y[j]) {
				// i --> j goes up
				if (utl != utr) {
					edges.emplace(min(utl, utr), max(utl, utr));
				}
			} else if (Y[i] == Y[j] && X[i] > X[j]) {
				// i --> j goes left
				if (ubl != utl) {
					edges.emplace(min(ubl, utl), max(ubl, utl));
				}
			} else if (Y[i] == Y[j] && X[i] < X[j]) {
				// i --> j goes right
				if (utr != ubr) {
					edges.emplace(min(utr, ubr), max(utr, ubr));
				}
			} else {
				assert(0);
			}
		}
	}
	for (auto [u, v] : edges) {
		adj2[u].pb(v);
		adj2[v].pb(u);
	}
	while (!leftmost.empty() || !upmost.empty()) {
		if (!leftmost.empty()) {
			source = ufds::find(tl(leftmost.begin()->second));
		} else {
			source = ufds::find(tl(upmost.rbegin()->second));
		}
		//~ cout << "SOURCE " << source << '\n';
		Q.push(source);
		vis[source] = 1;
		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			for (auto v : adj2[u]) {
				if (!vis[v]) {
					//~ cout << "VIS " << v << '\n';
					vis[v] = 1;
					dist[v] = dist[u] + 1;
					Q.push(v);
				}
			}
		}
		while (!leftmost.empty()) {
			if (vis[ufds::find(tl(leftmost.begin()->second))]) leftmost.erase(leftmost.begin());
			else break;
		}
		while (!upmost.empty()) {
			if (vis[ufds::find(tl(upmost.rbegin()->second))]) upmost.erase(--upmost.end());
			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.pb(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.pb(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.pb(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.pb(i);
		} else {
			assert(0);
		}
	}
	cout << standing.size() << '\n';
	for (auto i : standing) {
		//~ cout << i << ": " << A[i] << ' ' << B[i] << '\n';
		cout << i << '\n';
	}
}

Compilation message (stderr)

flood.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | 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: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9