Submission #621026

#	Time	Username	Problem	Language	Result	Execution time	Memory
621026		MKopchev	Fountain Parks (IOI21_parks)	C++17	30 / 100	414 ms	39656 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=2e5+42;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

map< pair<int,int>, int > seen;

int ask(int x,int y)
{
    if(seen.count({x,y}))return seen[{x,y}];

    return -1;
}

int parent[nmax];

int root(int node)
{
    if(node==parent[node])return node;

    parent[node]=root(parent[node]);

    return parent[node];
}

set< pair<int,int> > benches;

struct point
{
    int x,y,id;
};

bool cmp(point a,point b)
{
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}

point inp[nmax];

int construct_roads(std::vector<int> x, std::vector<int> y) {

    int n=x.size();

    if (n == 1) {
	build({}, {}, {}, {});
        return 1;
    }

    for(int i=0;i<x.size();i++)
        seen[{x[i],y[i]}]=i;

    for(int i=0;i<n;i++)
    {
        parent[i]=i;

        inp[i].x=x[i];
        inp[i].y=y[i];
        inp[i].id=i;
    }

    sort(inp,inp+n,cmp);

    vector<int> u={},v={},a={},b={};

    for(int j=0;j<n;j++)
    {
        int pos=ask(inp[j].x+2,inp[j].y);

        if(pos!=-1&&root(pos)!=root(inp[j].id))
        {
            parent[root(pos)]=root(inp[j].id);

            u.push_back(inp[j].id);
            v.push_back(pos);

            pair<int,int> bench={inp[j].x+1,inp[j].y-1};

            if(benches.count(bench))bench.second+=2;

            a.push_back(bench.first);
            b.push_back(bench.second);

            benches.insert(bench);
        }

        pos=ask(inp[j].x,inp[j].y+2);

        if(pos!=-1&&root(pos)!=root(inp[j].id))
        {
            parent[root(pos)]=root(inp[j].id);

            u.push_back(inp[j].id);
            v.push_back(pos);

            pair<int,int> bench={inp[j].x-1,inp[j].y+1};

            if(benches.count(bench))bench.first+=2;

            a.push_back(bench.first);
            b.push_back(bench.second);

            benches.insert(bench);
        }
    }

    for(int i=0;i<n;i++)
        if(root(i)!=root(0))return 0;

    build(u,v,a,b);

    return 1;
}

/*
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()");
	_u = u;
	_v = v;
	_a = a;
	_b = b;
}

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("%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;
}
*/

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

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