Submission #894879

#	Time	Username	Problem	Language	Result	Execution time	Memory
894879		Jawad_Akbar_JJ	Fountain Parks (IOI21_parks)	C++17	15 / 100	105 ms	49560 KiB

parks

#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);
	}
}

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;

	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:91:5: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |  dfs(k,mny);
      |  ~~~^~~~~~~

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