Submission #439200

#	Time	Username	Problem	Language	Result	Execution time	Memory
439200		FSYo	Fountain Parks (IOI21_parks)	C++17	70 / 100	803 ms	138480 KiB

parks

#include<bits/stdc++.h>
#include "parks.h"
#define cs const
#define pb push_back
using namespace std;
typedef vector<int> vi; 
typedef long long ll;
typedef pair<int, int> pi; 
cs int N = 4e5 + 5; 
int n, fa[N];
map<int, int> c[N], e[N];
vector<pi> E; 
int fnd(int x) {
	if(x == fa[x]) return x; 
	return fa[x] = fnd(fa[x]);
}
void mer(int a, int b) {
	if(a < 0) return;
	if(fnd(a) == fnd(b)) return;
	E.pb(pi(a, b));
	e[a][b] = e[b][a] = E.size() - 1; 
	fa[fnd(a)] = fnd(b);
}
vector<int> G[N];
int dfn[N], low[N], tim;
int s[N], top, in[N], blk[N], m;

void dfs(int x) {
	dfn[x] = low[x] = ++ tim; 
	s[++top] = x, in[x] = 1; 
	for(int v : G[x]) {
		if(!dfn[v]) dfs(v), low[x] = min(low[x], low[v]);
		else if(in[v] && dfn[v] < low[x]) low[x] = dfn[v];
	}
	if(low[x] == dfn[x]) {
		++ m; do {
			in[s[top]] = 0;
			blk[s[top]] = m; 
		} while(s[top--] != x);
	}
}

#ifdef FSYo
void build(vi u, vi v, vi a, vi b) {
	int m = u.size();
	cout << m << endl;
//	map<pi, int> tt; 
//	for(int i = 0; i < m; i++) {
//		cout <<i<<' '<< x[u[i]] << " " << y[u[i]] << ' ' << x[v[i]] << ' ' << y[v[i]] << ' ' << a[i] << ' ' << b[i] << '\n';
//		for(int v : G[i]) cout << v << ' ';cout <<endl;
//		assert(tt[pi(a[i], b[i])] == 0);
//		tt[pi(a[i], b[i])] = 1; 
//	}
}
#endif

int construct_roads(vi x, vi y) {
	n = x.size();
	for(int i = 0; i < n; i++)
		c[x[i]][y[i]] = i + 1; 
	for(int i = 0; i < n; i++) fa[i] = i; 
	for(int x = 2; x <= 2e5; x += 2) 
	for(auto p : c[x]) {
		int y = p.first, t = p.second; 
		mer(c[x - 2][y] - 1, t - 1);
		mer(c[x][y - 2] - 1, t - 1);
	}
	if(E.size() < n - 1) return 0; 
	for(int i = 0; i < n - 1; i++) {
		int u = E[i].first, v = E[i].second; 
		if(x[u] != x[v]) continue; 
		if(y[u] > y[v]) swap(u, v);
		int a = c[x[u] - 2][y[u]] - 1, z = -1; 
		if(~a) z = e[a][u];
		if(~z) {
			G[i].pb(z);
			G[z + n - 1].pb(i + n - 1);
		} 
		z = -1; 
		a = c[x[u] + 2][y[u]] - 1; 
		if(~a) z = e[a][u];
		if(~z) {
			G[i + n - 1].pb(z);
			G[z + n - 1].pb(i);
		}
		z = -1;
		a = c[x[v] - 2][y[v]] - 1;
		if(~a) z = e[a][v];
		if(~z) {
			G[i].pb(z + n - 1);
			G[z].pb(i + n - 1);
		}
		z = -1;
		a = c[x[v] + 2][y[v]] - 1;
		if(~a) z = e[a][v];
		if(~z) {
			G[i + n - 1].pb(z + n - 1);
			G[z].pb(i);
		}
		z = -1; 
		a = c[x[u] + 2][y[u]] - 1;
		int b = c[x[v] + 2][y[v]] - 1; 
		if(~a && ~b) z = e[a][b];
		if(~z) {
			G[i + n - 1].pb(z + n - 1);
			G[z].pb(i);
		}
	}
	for(int i = 0; i < n - 1; i++) {
		int u = E[i].first, v = E[i].second; 
		if(y[u] != y[v]) continue; 
		if(x[u] > x[v]) swap(u, v);
		int a = c[x[u]][y[u] + 2] - 1, z = -1; 
		int b = c[x[v]][y[v] + 2] - 1; 
		if(~a && ~b) z = e[a][b];
		if(~z) {
			G[i + n - 1].pb(z + n - 1);
			G[z].pb(i);
		}
	}
	for(int i = 0; i < (n - 1) * 2; i++)
		if(!dfn[i]) dfs(i);
	vi u(n - 1), v(n - 1), a(n - 1), b(n - 1);
	for(int i = 0, o; i < n - 1; i++) {
		u[i] = E[i].first, v[i] = E[i].second;
		o = blk[i + n - 1] < blk[i];
		if(x[u[i]] == x[v[i]]) {
			b[i] = min(y[u[i]], y[v[i]]) + 1;
			a[i] = x[u[i]] + (o ? 1 : -1);
		}
		else {
			a[i] = min(x[u[i]], x[v[i]]) + 1; 
			b[i] = y[u[i]] + (o ? 1 : -1);
		}
	}
	build(u, v, a, b);
	return 1; 
}
#ifdef FSYo
int main() {
	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	int n; 
	cin >> n; 
	vi x(n), y(n);
	for(int i = 0; i < n; i++)
		scanf("%d%d", &x[i], &y[i]);
	if(construct_roads(x, y)) {
		puts("YES");
	}
	else puts("NO");
	
	return 0; 
}
#endif

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(vi, vi)':
parks.cpp:68:14: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |  if(E.size() < n - 1) return 0;
      |     ~~~~~~~~~^~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30