Submission #720169

#	Time	Username	Problem	Language	Result	Execution time	Memory
720169		marvinthang	Flood (IOI07_flood)	C++17	100 / 100	127 ms	14752 KiB

flood

/*************************************
*    author: marvinthang             *
*    created: 23.08.2022 21:58:31    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int MAX = 1e5 + 5;

struct Point {
	int x, y, in_comp;
	pair <int, int> nxt[4];
	int region[4];
	Point() {
		x = y = in_comp = -1;
		for (int i = 0; i < 4; ++i) {
			nxt[i] = make_pair(-1, -1);
			region[i] = -1;
		}
	}
	friend scan_op(Point) { return in >> u.x >> u.y; }
} points[MAX];

struct Region {
	int flood_time = -1;
	long long area = 0;
	vector <int> points;
};

int get_dir(int a, int b) {
	if (points[a].y == points[b].y) 
		return points[a].x < points[b].x ? 0 : 2;
	return points[a].y > points[b].y ? 1 : 3;
}

int N, M;

void init(void) {
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> points[i];
	cin >> M;
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b; --a; --b;
		points[a].nxt[get_dir(a, b)] = make_pair(b, i);
		points[b].nxt[get_dir(b, a)] = make_pair(a, i);
	}
}

void bfs(int s, int lab) {
	queue <int> q;
	points[s].in_comp = lab;
	q.push(s);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < 4; ++i) {
			int v = points[u].nxt[i].fi;
			if (~v && !~points[v].in_comp) {
				points[v].in_comp = lab;
				q.push(v);
			}
		}
	}
}

void dfs(int i, int j, Region &r, int lab) {
	r.points.push_back(i);
	while (!~points[i].region[j]) {
		points[i].region[j] = lab;
		int k = points[i].nxt[j].fi;
		r.points.push_back(k);
		r.area += 1LL * (points[i].x - points[k].x) * (points[i].y + points[k].y);
		i = k;
		j = (j + 3) % 4;
		while (!~points[i].nxt[j].fi) j = (j + 1) % 4;
	}
	if (r.area < 0) r.area = -r.area;
}

void process(void) {
	int numComp = 0;
	for (int i = 0; i < N; ++i) if (points[i].in_comp == -1)
		bfs(i, numComp++);
	vector <int> start_region(numComp, -1);
	vector <Region> regions;
	for (int i = 0; i < N; ++i) for (int j = 0; j < 4; ++j) {
		if (!~points[i].nxt[j].fi || ~points[i].region[j]) continue;
		int lab = regions.size();
		regions.push_back(Region());
		dfs(i, j, regions[lab], lab);
		int &tmp = start_region[points[i].in_comp];
		if (!~tmp || regions[tmp].area < regions[lab].area) tmp = lab;
	}
	queue <int> q;
	for (int i = 0; i < numComp; ++i) {
		int u = start_region[i];
		if (!~u) continue;
		regions[u].flood_time = 0;
		q.push(u);
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 1; i < regions[u].points.size(); ++i) {
			int a = regions[u].points[i - 1];
			int b = regions[u].points[i];
			int v = points[b].region[get_dir(b, a)];
			if (regions[v].flood_time == -1) {
				regions[v].flood_time = regions[u].flood_time + 1;
				q.push(v);
			}
		}
	}
	vector <int> res;
	for (int u = 0; u < N; ++u) for (int i = 0; i < 4; ++i) {
		int v = points[u].nxt[i].fi;
		if (!~v || v < u) continue;
		if (regions[points[u].region[get_dir(u, v)]].flood_time == 
			regions[points[v].region[get_dir(v, u)]].flood_time)
			res.push_back(points[u].nxt[i].se);
	}
	cout << res.size() << '\n';
	for (int x: res) cout << x + 1 << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("flood");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message (stderr)

flood.cpp: In function 'void process()':
flood.cpp:125:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for (int i = 1; i < regions[u].points.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp: In function 'int main()':
flood.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:149:2: note: in expansion of macro 'file'
  149 |  file("flood");
      |  ^~~~
flood.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:149:2: note: in expansion of macro 'file'
  149 |  file("flood");
      |  ^~~~

• 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