Submission #1316493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316493		g4yuhg	Flood (IOI07_flood)	C++20	100 / 100	173 ms	29816 KiB

flood

#include<bits/stdc++.h>
//#include "minesweeper.h"
typedef int ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 1000006
#define endl '\n'
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

ll n, m;
pii a[N];

ll side[N][4][2], d[N], xof[N];

set<pii> s;

vector<ll> adj[N];

void pre() {
	cin >> m;
	for (int i = 1; i <= m; i ++) {
		ll u, v;
		cin >> u >> v;
		if (a[u].fi == a[v].fi) { // doc
			if (a[u].se > a[v].se) swap(u, v);
			side[u][1][0] = i; // 0: di ra // 1: di vao
			side[u][1][1] = i + m;
			side[v][3][0] = i + m;
			side[v][3][1] = i;
			xof[i] = a[u].fi;
		}
		else { // ngang
			if (a[u].fi > a[v].fi) swap(u, v);
			side[u][0][0] = i;
			side[u][0][1] = i + m;
			side[v][2][0] = i + m;
			side[v][2][1] = i;
			xof[i] = inf;
		}
		s.insert({xof[i], i});
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j < 4; j ++) {
			if (side[i][j][1]) {
				ll jj = j;
				if (j == 1) jj = 3;
				if (j == 3) jj = 1;
				if (j == 2) jj = 0;
				if (j == 0) jj = 2;
				for (int k = (jj - 1 + 4) % 4;; k = (k + 1) % 4) {
					if (side[i][k][0]) {
						ll x = side[i][j][1];
						ll y = side[i][k][0];
						adj[x].push_back(y);
						adj[y].push_back(x);
						//cout << "i: " << i << " " << j << " " << k << endl;
						//cout << " x y: " << x << " " << y << endl;
						break;
					}
				}
			}
		}
	}
	for (int i = 1; i <= m + m; i ++) {
		d[i] = inf;
	}
	while (s.size()) {
		pii xet = *s.begin();
		s.erase(xet);
		deque<pii> dq;
		xet.se = xet.se + m;
		d[xet.se] = 0;
		dq.push_front({d[xet.se], xet.se});
		while (dq.size()) {
			ll u = dq.front().se, c = dq.front().fi; dq.pop_front();
			//cout << " c u " << c << " " << u << endl;
			if (u <= m) {
				if (s.find({xof[u], u}) != s.end()) {
					s.erase({xof[u], u});
				}
			}
			if (c > d[u]) continue;
			for (auto v : adj[u]) {
				if (d[v] > d[u]) {
					d[v] = d[u];
					dq.push_front({d[v], v});
				}
			}
			ll nguoc;
			if (u <= m) nguoc = u + m;
			else nguoc = u - m;
			if (d[nguoc] > d[u] + 1) {
				d[nguoc] = d[u] + 1;
				dq.push_back({d[nguoc], nguoc});
			}
		}
	}
	vector<ll> res;
	for (int i = 1; i <= m; i ++) {
		if (d[i] == d[i + m]) {
			res.push_back(i);
			//cout << "i " << i << " " << d[i] << endl;
		}
	}
	cout << res.size() << endl;
	for (auto it : res) {
		cout << it << endl;
	}
}

bool klinh;

signed main() {
	if (fopen("kghmdlod.inp", "r")) {
		freopen("kghmdlod.inp", "r", stdin);
		freopen("kghmdlod.out", "w", stdout);
	}
	srand(time(0));
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].fi >> a[i].se;
	}
	pre();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:120:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 freopen("kghmdlod.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen("kghmdlod.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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