Submission #815331

#	Time	Username	Problem	Language	Result	Execution time	Memory
815331		I_Love_EliskaM_	Fountain Parks (IOI21_parks)	C++17	70 / 100	611 ms	30416 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second

struct DSU {
	vector<int> p,sz;
	int tot;
	DSU(int n) {
		forn(i,n) p.pb(i), sz.pb(1);
		tot=n;
	}
	int get(int u) {
		return p[u]==u?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u), v=get(v);
		if (sz[u]<sz[v]) swap(u,v);
		sz[u]+=sz[v];
		p[v]=u;
		--tot;
	}
};

int p3(vector<int> x, vector<int> y) {

	int n=x.size();
	vector<int> u,v,a,b;
	map<pi,int> m;
	forn(i,n) m[{x[i],y[i]}]=i;
	DSU dsu(n);

	vector<pi> z1={{0,-2},{0,2}};
	vector<pi> z2={{-2,0},{2,0}};
	forn(i,n) {
		int f=x[i], s=y[i];
		for(auto&x:z1) {
			if (m.count({f+x.f,s+x.s})) {
				if (i<m[{f+x.f,s+x.s}]) {
					if (dsu.get(i)==dsu.get(m[{f+x.f,s+x.s}])) continue;
					dsu.uni(i,m[{f+x.f,s+x.s}]);
					u.pb(i), v.pb(m[{f+x.f,s+x.s}]);
				}
			}
		}
	}
	forn(i,n) {
		int f=x[i], s=y[i];
		for(auto&x:z2) {
			if (m.count({f+x.f,s+x.s})) {
				if (i<m[{f+x.f,s+x.s}]) {
					if (dsu.get(i)==dsu.get(m[{f+x.f,s+x.s}])) continue;
					dsu.uni(i,m[{f+x.f,s+x.s}]);
					u.pb(i), v.pb(m[{f+x.f,s+x.s}]);
				}
			}
		}
	}
	if (u.size()!=n-1) return 0;

	forn(i,n-1) {
		int x1=x[u[i]], y1=y[u[i]];
		int x2=x[v[i]], y2=y[v[i]];
		if (x1==x2) {
			if (x1==2) {
				a.pb(1);
				b.pb(max(y1,y2)-1);
			} else if (x1==6) {
				a.pb(7);
				b.pb(max(y1,y2)-1);
			} else {
				if (max(y1,y2)%4) {
					a.pb(3);
					b.pb(max(y1,y2)-1);
				} else {
					a.pb(5);
					b.pb(max(y1,y2)-1);
				}
			}
		} else {
			if ((max(x1,x2)+y1)%4) {
				a.pb(max(x1,x2)-1);
				b.pb(y1+1);
			} else {
				a.pb(max(x1,x2)-1);
				b.pb(y1-1);
			}
		}
	}
	build(u,v,a,b);
	return 1;
}

int construct_roads(vector<int> x, vector<int> y) {
	int mx=0; for(auto&v:x) mx=max(mx,v);
	if (mx<=6) return p3(x,y);

	int n=x.size();
	vector<int> u,v,a,b;
	map<pi,int> m;
	forn(i,n) m[{x[i],y[i]}]=i;
	DSU dsu(n);

	vector<pi> z={{-2,0},{2,0},{0,-2},{0,2}};
	forn(i,n) {
		int f=x[i], s=y[i];
		for(auto&x:z) {
			if (m.count({f+x.f,s+x.s})) {
				if (i<m[{f+x.f,s+x.s}]) {
					if (dsu.get(i)==dsu.get(m[{f+x.f,s+x.s}])) continue;
					dsu.uni(i,m[{f+x.f,s+x.s}]);
					u.pb(i), v.pb(m[{f+x.f,s+x.s}]);
				}
			}
		}
	}
	if (u.size()!=n-1) return 0;
	
	forn(i,n-1) {
		int x1=x[u[i]], y1=y[u[i]];
		int x2=x[v[i]], y2=y[v[i]];
		if (x1==x2) {
			if ((max(y1,y2)+x1)%4) {
				a.pb(x1+1);
				b.pb(max(y1,y2)-1);
			} else {
				a.pb(x1-1);
				b.pb(max(y1,y2)-1);
			}
		} else {
			if ((max(x1,x2)+y1)%4) {
				a.pb(max(x1,x2)-1);
				b.pb(y1-1);
			} else {
				a.pb(max(x1,x2)-1);
				b.pb(y1+1);
			}
		}
	}
	build(u,v,a,b);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int p3(std::vector<int>, std::vector<int>)':
parks.cpp:64:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |  if (u.size()!=n-1) return 0;
      |      ~~~~~~~~^~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:122:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |  if (u.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