Submission #620995

#	Time	Username	Problem	Language	Result	Execution time	Memory
620995		MKopchev	Fountain Parks (IOI21_parks)	C++17	15 / 100	751 ms	46596 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;

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;

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

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

        if(pos!=-1)
        {
            parent[root(pos)]=root(i);

            u.push_back(i);
            v.push_back(pos);

            pair<int,int> bench={x[i]+1,y[i]+1};

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

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

            benches.insert(bench);
        }

        pos=ask(x[i],y[i]+2);

        if(pos!=-1)
        {
            parent[root(pos)]=root(i);

            u.push_back(i);
            v.push_back(pos);

            pair<int,int> bench={x[i]+1,y[i]+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:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

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