Submission #894884

#	Time	Username	Problem	Language	Result	Execution time	Memory
894884		Jawad_Akbar_JJ	Fountain Parks (IOI21_parks)	C++17	0 / 100	0 ms	348 KiB

parks

// #include <iostream>
// #include <vector>

// using namespace std;











// // #include "parks.h"
// #include <cstdio>
// #include <cmath>
// #include <cassert>
// #include <vector>
// #include <string>
// using namespace std;


// static void check(bool cond, string message) {
// 	if (!cond) {
// 		printf("%s\n", message.c_str());
// 		fclose(stdout);
// 		exit(0);
// 	}
// }

// static int n;
// static bool build_called;
// static int m;
// static vector<int> _u, _v, _a, _b;

// void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
// 	check(!build_called, "build is called more than once");
// 	build_called = true;
// 	m = u.size();
// 	check(int(v.size()) == m, "u.size() != v.size()");
// 	check(int(a.size()) == m, "u.size() != a.size()");
// 	check(int(b.size()) == m, "u.size() != b.size()");
// 	check(m <= 2*n, "Construction too large"); // Vertex degrees are at most 4
// 	_u = u;
// 	_v = v;
// 	_a = a;
// 	_b = b;
// }














// const int N = 200000 + 10;

// int seen[10][N];
// int seen2[10][N];
// int used[12][N];

// int sn =  0;

// vector<pair<int,int>> d = {{0,2},{2,0},{-2,0},{0,-2}};

// vector<int> a,b,X,Y;
// vector<pair<int,int>> up,nup;

// void dfs(int i,int j){
// 	seen2[i][j] = true;
// 	sn++;
// 	for (auto [x,y] : d){
// 		int ni = i + x;
// 		int nj = j + y;
// 		if (!seen[ni][nj] or seen2[ni][nj])
// 			continue;
// 		if (i==ni)
// 			up.push_back({seen[i][j]-1,seen[ni][nj]-1});
// 		else
// 			nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
// 		dfs(ni,nj);
// 	}
// }

// pair<int,int> det(int x1,int y1,int x2,int y2){
// 	if (x1 == x2){
// 		if (y1>y2)
// 			swap(y1,y2);
// 		if (x1 == 2)
// 			return {1,y1+1};
// 		if (x1 == 6)
// 			return {7,y1+1};
// 		if (used[3][y1-1] or used[3][y2 + 1])
// 			return {5,y1 + 1};
// 		return {3,y1 + 1};
// 	}
// 	if (x1>x2)
// 		swap(x1,x2);

// 	if (used[x1+1][y1-1])
// 		return {x1+1,y1+1};
// 	return {x1+1,y1-1};
// }

// int construct_roads(vector<int> x,vector<int> y){
// 	int n = x.size();
// 	int mny = 1e7,k;
// 	for (int i=0;i<n;i++){
// 		seen[x[i]][y[i]] = i+1;
// 		if (y[i]<mny)
// 			mny = y[i],k = x[i];
// 	}

// 	dfs(k,mny);

// 	if (sn!=n)
// 		return 0;


// 	for (auto [i,j] : up){
// 		auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
// 		used[ii][jj] = true;
// 		a.push_back(i);
// 		b.push_back(j);
// 		X.push_back(ii);
// 		Y.push_back(jj);
// 	}
// 	for (auto [i,j] : nup){
// 		auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
// 		used[ii][jj] = true;
// 		a.push_back(i);
// 		b.push_back(j);
// 		X.push_back(ii);
// 		Y.push_back(jj);
// 	}

// 	build(a,b,X,Y);
// 	return 1;
// }



// int main() {
// 	assert(scanf("%d", &n) == 1);
// 	vector<int> x(n), y(n);
// 	for (int i = 0; i < n; i++) {
// 		assert(scanf("%d%d", &x[i], &y[i]) == 2);
// 	}
// 	fclose(stdin);

// 	build_called = false;
// 	const int possible = construct_roads(x, y);

// 	check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
// 	if (possible == 1) {
// 		check(build_called, "construct_roads() returned 1 without calling build()");
// 	} else {
// 		check(!build_called, "construct_roads() called build() but returned 0");
// 	}

// 	printf("OK\n");
// 	printf("%d\n", possible);
// 	if (possible == 1) {
// 		printf("%d\n", m);
// 		for (int j = 0; j < m; j++) {
// 			printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
// 		}
// 	}
// 	fclose(stdout);
// 	return 0;
// }

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;











#include "parks.h"
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>









const int N = 200000 + 10;

int seen[10][N];
int seen2[10][N];
int used[12][N];

int sn =  0;

vector<pair<int,int>> d = {{0,2},{2,0},{-2,0},{0,-2}};

vector<int> a,b,X,Y;
vector<pair<int,int>> up,nup;

void dfs(int i,int j){
	seen2[i][j] = true;
	sn++;
	for (auto [x,y] : d){
		int ni = i + x;
		int nj = j + y;
		if (!seen[ni][nj] or seen2[ni][nj])
			continue;
		if (i==ni and i==4)
			up.push_back({seen[i][j]-1,seen[ni][nj]-1});
		else
			nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
		dfs(ni,nj);
	}
}

void dfs2(int i,int j){
	if (seen2[i][j])
		return;
	seen2[i][j] = true;
	sn++;
	int ni = i;
	int nj = j + 2;
	if (!seen[ni][nj] or seen2[ni][nj])
		return;
	nup.push_back({seen[i][j]-1,seen[ni][nj]-1});
	dfs2(ni,nj);
}

pair<int,int> det(int x1,int y1,int x2,int y2){
	if (x1 == x2){
		if (y1>y2)
			swap(y1,y2);
		if (x1 == 2)
			return {1,y1+1};
		if (x1 == 6)
			return {7,y1+1};
		if (used[3][y1-1] or used[3][y2 + 1])
			return {5,y1 + 1};
		return {3,y1 + 1};
	}
	if (x1>x2)
		swap(x1,x2);

	if (used[x1+1][y1-1])
		return {x1+1,y1+1};
	return {x1+1,y1-1};
}

int construct_roads(vector<int> x,vector<int> y){
	int n = x.size();
	int mny = 1e7,k;
	for (int i=0;i<n;i++){
		if (x[i]==2 or x[i]==6)
			dfs2(x[i],y[i]);
	}

	for (int i=0;i<n;i++){
		if (!seen2[x[i]][y[i]])
			dfs(x[i],y[i]);
	}

	if (sn!=n)
		return 0;

	sort(begin(up),end(up));
	for (auto [i,j] : up){
		auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
		used[ii][jj] = true;
		a.push_back(i);
		b.push_back(j);
		X.push_back(ii);
		Y.push_back(jj);
	}
	for (auto [i,j] : nup){
		auto [ii,jj] = det(x[i],y[i],x[j],y[j]);
		used[ii][jj] = true;
		a.push_back(i);
		b.push_back(j);
		X.push_back(ii);
		Y.push_back(jj);
	}

	build(a,b,X,Y);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:277:6: warning: unused variable 'mny' [-Wunused-variable]
  277 |  int mny = 1e7,k;
      |      ^~~
parks.cpp:277:16: warning: unused variable 'k' [-Wunused-variable]
  277 |  int mny = 1e7,k;
      |                ^

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