Submission #894882

#	Time	Username	Problem	Language	Result	Execution time	Memory
894882		Jawad_Akbar_JJ	Fountain Parks (IOI21_parks)	C++17	0 / 100	1 ms	348 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);
	}
}
 
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;
	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});
	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]);
	}
 
	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:111:5: warning: 'k' is used uninitialized in this function [-Wuninitialized]
  111 |  dfs(k,mny);
      |  ~~~^~~~~~~

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