Submission #1040871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040871		yanb	Fountain Parks (IOI21_parks)	C++17	45 / 100	136 ms	25284 KiB

parks

#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include "parks.h"


using namespace std;

vector<int> x, y;
vector<int> north, south, east, west;
vector<int> visited;

bool cmpx(int i, int j) {
	if (x[i] == x[j])
		return (y[i] < y[j]);
	return (x[i] < x[j]);
}

bool cmpy(int i, int j) {
	if (y[i] == y[j])
		return (x[i] < x[j]);
	return (y[i] < y[j]);
}



void RunDFS(int s) {
    vector<int> stack;
//    cout << s << visited[s] << " north: " << north[s] << " east: " << east[s] << " south: " << south[s] << " west: " << west[s] << endl;
    stack.push_back(s);
    while (stack.size() > 0) {
	    int t = stack.back();
	    stack.pop_back();
	    if (visited[t] != 1) {
		    visited[t]=1;
		    if(north[t] != -1) stack.push_back(north[t]);
      	 	    if(west[t] != -1) stack.push_back(west[t]);
	            if(south[t] != -1) stack.push_back(south[t]);
       		    if(east[t] != -1) stack.push_back(east[t]);
	    }
    }
}

/*
void RunDFS(int s) {
    if(visited[s] == 1) return;
    visited[s]=1;
    if(north[s] != -1) RunDFS(north[s]);
    if(west[s] != -1) RunDFS(west[s]);
    if(south[s] != -1) RunDFS(south[s]);
    if(east[s] != -1) RunDFS(east[s]);
}
*/

// Edge set and tree set
std::vector<int> u, v, a, b;

void add_edge(int i, int j) {
	u.push_back(i);
	v.push_back(j);
//	cout << "merge " << i << "," << j << endl;
	if (((x[i]+y[i])/2) % 2 == 0) {
		// insert tree on left
		if (x[i] == x[j]) {
			b.push_back( (y[i]+y[j])/2 );
			if (y[j] > y[i]) {
				a.push_back(x[i]-1);
			} else {
				a.push_back(x[i]+1);
			}
		} else {
			a.push_back( (x[i]+x[j])/2 );
			if (x[j] > x[i]) {
				b.push_back(y[i]+1);
			} else {
				b.push_back(y[i]-1);
			}
		}
	} else {
		// insert tree on right
		if (x[i] == x[j]) {
			b.push_back( (y[i]+y[j])/2 );
			if (y[j] > y[i]) {
				a.push_back(x[i]+1);
			} else {
				a.push_back(x[i]-1);
			}
		} else {
			a.push_back( (x[i]+x[j])/2 );
			if (x[j] > x[i]) {
				b.push_back(y[i]-1);
			} else {
				b.push_back(y[i]+1);
			}
		}
	}
}

/*
void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b) {
	return 0;
}
*/

int construct_roads(std::vector<int> _x, std::vector<int> _y) {
	x = _x;
	y = _y;
	std::vector<int> idx;

	int n = x.size();

	for(int i=0; i<n; i++) {
		idx.push_back( i );
	}

	/*
	cout << "The vector before applying sort is:\n" ;
	for (int i=0; i<n; i++) {
		cout << idx[i] << ": " << x[idx[i]] << " " << y[idx[i]] << endl;
	}
	*/


	for (int i=0; i<n; i++) {
		north.push_back(-1);
		south.push_back(-1);
		east.push_back(-1);
		west.push_back(-1);
	}


	// Assign north & south
	std::sort(idx.begin(), idx.end(), cmpx);
	for (int i=0; i<n-1; i++) {
		if (x[idx[i]]==x[idx[i+1]] && y[idx[i]]+2 == y[idx[i+1]]) {
			add_edge(idx[i], idx[i+1]);
			north[idx[i]] = idx[i+1];
			south[idx[i+1]] = idx[i];
		}
	}

	// Assign east & west
	std::sort(idx.begin(), idx.end(), cmpy);
	for (int i=0; i<n-1; i++) {
		if (y[idx[i]]==y[idx[i+1]] && x[idx[i]]+2 == x[idx[i+1]]) {
			add_edge(idx[i], idx[i+1]);
			east[idx[i]] = idx[i+1];
			west[idx[i+1]] = idx[i];
		}
	}

//	cout << "Finish assigning directions\n";

	for(int i=0; i<n; i++) {
		visited.push_back(-1);
	}
	RunDFS(0);

	bool connected = true;
	for(int i=0; i<n; i++) {
		if (visited[i] == -1) {
			connected = false;
			break;
		}
	}
	if (connected == false) {
//		cout << "It is not connected" << endl;
		return 0;
	}
//	cout << "It is connected" << endl;


	build(u, v, a, b);

	return 1;
}

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