Submission #199656

#	Time	Username	Problem	Language	Result	Execution time	Memory
199656		sjimed	Flood (IOI07_flood)	C++14	30 / 100	532 ms	26208 KiB

flood

#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;  
const int inf = 1e9;

int n, m;
pii a[100010];
vector<pii> x, y;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int con[400010][4];
int w[400010][4];
int chk[400010];
deque<pii> dq;
bool ans[400010];

int main() {
	fast;

	cin >> n;

	x.eb(-1, -1);

	for(int i=1; i<=n; i++) {
		cin >> a[i].fi >> a[i].se;

		for(int k=0; k<4; k++) {
			x.eb(a[i].fi + k/2, a[i].se + k%2);
		}
	}

	y = x;

	sort(all(x));
	x.erase(unique(all(x)), x.end());
	
	sort(all(y));
	y.erase(unique(all(y)), y.end());
	sort(all(y), [](pii i, pii j) {
		return i.se != j.se ? i.se < j.se : i.fi < j.fi;
	});

	for(int i=0; i<x.size(); i++) {
		if(i > 0 && x[i-1].fi == x[i].fi) {
			con[i][3] = i-1;
		}
		
		if(i+1 < x.size() && x[i].fi == x[i+1].fi) {
			con[i][2] = i+1;
		}
		
	}

	for(int i=0; i<y.size(); i++) {
		if(i > 0 && y[i-1].se == y[i].se) {
			con[lower_bound(all(x), y[i]) - x.begin()][1] = lower_bound(all(x), y[i-1]) - x.begin();
		}
		
		if(i+1 < y.size() && y[i].se == y[i+1].se) {
			con[lower_bound(all(x), y[i]) - x.begin()][0] = lower_bound(all(x), y[i+1]) - x.begin();
		}
	}

	cin >> m;

	for(int i=1; i<=m; i++) {
		int u, v;
		cin >> u >> v;

		if(a[u] > a[v]) swap(u, v);

		if(a[u].fi != a[v].fi) {
			w[lower_bound(all(x), mp(a[u].fi+1, a[u].se)) - x.begin()][2] = i;
			w[lower_bound(all(x), mp(a[u].fi+1, a[u].se+1)) - x.begin()][3] = i;
			w[lower_bound(all(x), mp(a[v].fi, a[v].se)) - x.begin()][2] = i;
			w[lower_bound(all(x), mp(a[v].fi, a[v].se+1)) - x.begin()][3] = i;
		}
		else {
			//cout << "????????????????" << a[u].fi << " " << a[u].se << " " << a[v].fi << " " << a[v].se << endl;
			w[lower_bound(all(x), mp(a[u].fi, a[u].se+1)) - x.begin()][0] = i;
			w[lower_bound(all(x), mp(a[u].fi+1, a[u].se+1)) - x.begin()][1] = i;
			w[lower_bound(all(x), mp(a[v].fi, a[v].se)) - x.begin()][0] = i;
			w[lower_bound(all(x), mp(a[v].fi+1, a[v].se)) - x.begin()][1] = i;
		}
	}

	/*for(int i=1; i<x.size(); i++) {
		cout << "(" << x[i].fi << " " << x[i].se << ") : ";

		for(int j=0; j<4; j++) {
			cout << "(" << x[con[i][j]].fi << " " << x[con[i][j]].se << ", " << w[i][j] << ") ";
		}

		cout << endl;
	}*/

	for(int i=1; i<x.size(); i++) {
		if(chk[i]) continue;

		dq.eb(i, 1);

		while(dq.size()) {
			int h = dq.front().fi;
			int cost = dq.front().se;
			dq.pop_front();

			if(chk[h]) continue;
			chk[h] = cost;

			//cout << "-----> " << x[h].fi << " " << x[h].se << " " << chk[h] << endl;

			for(int i=0; i<4; i++) {
				if(con[h][i] == 0 || chk[con[h][i]]) continue;

				if(w[h][i]) dq.eb(con[h][i], chk[h]+1);
				else dq.emplace_front(con[h][i], chk[h]);
			}
		}
	}

	for(int i=1; i<x.size(); i++) {
		//cout << x[i].fi << " " << x[i].se << " : " << chk[i] << endl;

		for(int j=0; j<4; j++) {
			if(con[i][j] > 0 && chk[con[i][j]] == chk[i]) ans[w[i][j]] = true;
		}
	}

	int cnt = 0;
	for(int i=1; i<=m; i++) {
		if(ans[i]) cnt++;
	}

	cout << cnt << "\n";

	for(int i=1; i<=m; i++) {
		if(ans[i]) cout << i << "\n";
	}
}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<x.size(); i++) {
               ~^~~~~~~~~
flood.cpp:61:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1 < x.size() && x[i].fi == x[i+1].fi) {
      ~~~~^~~~~~~~~~
flood.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<y.size(); i++) {
               ~^~~~~~~~~
flood.cpp:72:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1 < y.size() && y[i].se == y[i+1].se) {
      ~~~~^~~~~~~~~~
flood.cpp:110:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<x.size(); i++) {
               ~^~~~~~~~~
flood.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<x.size(); i++) {
               ~^~~~~~~~~

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