Submission #1224484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224484		nikulid	Fountain Parks (IOI21_parks)	C++20	15 / 100	193 ms	26368 KiB

parks

#include "parks.h"
#include <iostream>

using namespace std;

#define pb push_back

/*
 
IOI 2024 q3 FOUNTAIN PARKS

I'll try to get subtasks 1,2,3 for 30/100
*/

int n;
vector<int> visitted;
vector<int> lrow(100005, 0), mrow(100005, 0), rrow(100005, 0);

void dfs(int i, int row, int y){
	cerr<<"#";
	visitted[i]=1;
	if(row==0){
		if(lrow[y-1]!=0 && !visitted[lrow[y-1]]){ // check ABOVE
			dfs(lrow[y-1], row, y-1);
		}
		if(mrow[y]!=0 && !visitted[mrow[y]]){ // chech RIGHT
			dfs(mrow[y], row+1, y);
		}
		if(lrow[y+1]!=0 && !visitted[lrow[y+1]]){ // check BELOW
			dfs(lrow[y+1], row, y+1);
		}
	} else if(row==1){
		if(mrow[y-1]!=0 && !visitted[mrow[y-1]]){ // check ABOVE
			dfs(mrow[y-1], row, y-1);
		}
		if(rrow[y]!=0 && !visitted[rrow[y]]){ // chech RIGHT
			dfs(rrow[y], row+1, y);
		}
		if(mrow[y+1]!=0 && !visitted[mrow[y+1]]){ // check BELOW
			dfs(mrow[y+1], row, y+1);
		}
		if(lrow[y]!=0 && !visitted[lrow[y]]){ // check LEFT
			dfs(lrow[y], row-1, y);
		}
	} else if(row==2){
		if(rrow[y-1]!=0 && !visitted[rrow[y-1]]){ // check ABOVE
			dfs(rrow[y-1], row, y-1);
		}
		if(rrow[y+1]!=0 && !visitted[rrow[y+1]]){ // check BELOW
			dfs(rrow[y+1], row, y+1);
		}
		if(mrow[y]!=0 && !visitted[mrow[y]]){ // check LEFT
			dfs(mrow[y], row-1, y);
		}
	}
}

int construct_roads(vector<int> x, vector<int> y) {
	n=x.size();
	if (n == 1) {
		build({}, {}, {}, {});
		return 1;
	}

	vector<int> u, v, a, b;

	// since all coordinates are even, we can compress by dividing everything by 2. 
	for(int i=0; i<n; i++){
		if(x[i]>6)return 0;
		if(x[i]==2){
			lrow[y[i]/2] = i+1;
		} else if(x[i]==4){
			mrow[y[i]/2] = i+1;
		} else if(x[i]==6){
			rrow[y[i]/2] = i+1;
		}
	}

	// start with a dfs to determine whether or not it is possible...
	visitted = vector<int>(n+1, 0);
	dfs(0, (x[0]/2)-1, y[0]/2);

	for(int i=1; i<=n; i++) if(!visitted[i])return 0;
	
	cerr<<"initial dfs passed!\n";

	for(int y=0; y<100005; y++){
		if(lrow[y]!=0 && lrow[y+1]!=0){
			// far left (vertical)
			u.pb(lrow[y]);
			v.pb(lrow[y+1]);
			// bench on the leftside
			a.pb(1);
			b.pb((2*y)+1);
		}
		if(rrow[y]!=0 && rrow[y+1]!=0){
			// far right (vertical)
			u.pb(rrow[y]);
			v.pb(rrow[y+1]);
			// bench on the rightside
			a.pb(7);
			b.pb((2*y)+1);
		}

		if(y%2==0){
			// left side will face inside
			if(mrow[y]!=0 && mrow[y+1]!=0){
				u.pb(mrow[y]);
				v.pb(mrow[y+1]);
				a.pb(3);
				b.pb((2*y)+1);
			}

			// right side will face up/down
			if(mrow[y]!=0 && rrow[y]!=0 && (mrow[max(0,y-1)]==0 || rrow[max(0,y-1)]==0)){
				// there should be a horizontal above.
				u.pb(mrow[y]);
				v.pb(rrow[y]);
				a.pb(5);
				b.pb((2*y)+1);
			} else if(mrow[y+1]!=0 && rrow[y+1]!=0 && (mrow[y]==0 || rrow[y]==0)){
				u.pb(mrow[y+1]);
				v.pb(rrow[y+1]);
				a.pb(5);
				b.pb((2*y)+1);
			}
		} else{
			// left side will face up/down
			if(lrow[y]!=0 && mrow[y]!=0 && (lrow[max(0, y-1)]==0 || rrow[max(0,y-1)]==0)){
				// there should be a horizontal above.
				u.pb(lrow[y]);
				v.pb(mrow[y]);
				a.pb(3);
				b.pb((2*y)+1);
			} else if(lrow[y+1]!=0 && mrow[y+1]!=0 && (lrow[y]==0 || mrow[y]==0)){
				// " below.
				u.pb(lrow[y+1]);
				v.pb(mrow[y+1]);
				a.pb(3);
				b.pb((2*y)+1);
			}
			// right side will face inside
			if(mrow[y]!=0 && mrow[y+1]!=0){
				u.pb(mrow[y]);
				v.pb(mrow[y+1]);
				a.pb(5);
				b.pb((2*y)+1);
			}
		}
	}	

	for(int i=0; i<v.size(); i++){
		u[i]--;
		v[i]--;
	}


	build(u, v, a, b);
	return 1;
}

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