Submission #621091

#	Time	Username	Problem	Language	Result	Execution time	Memory
621091		MKopchev	Fountain Parks (IOI21_parks)	C++17	70 / 100	1235 ms	128676 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];

map<int, set< pair<int,int> > > from;
map< pair<int,int>, set<int> > to;

priority_queue< pair<int, pair<int,int> > > pq;

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);

            from[u.size()].insert({inp[j].x+1,inp[j].y+1});
            from[u.size()].insert({inp[j].x+1,inp[j].y-1});

            to[{inp[j].x+1,inp[j].y+1}].insert(u.size());
            to[{inp[j].x+1,inp[j].y-1}].insert(u.size());

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

            a.push_back(0);
            b.push_back(0);
        }

        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);

            from[u.size()].insert({inp[j].x+1,inp[j].y+1});
            from[u.size()].insert({inp[j].x-1,inp[j].y+1});

            to[{inp[j].x+1,inp[j].y+1}].insert(u.size());
            to[{inp[j].x-1,inp[j].y+1}].insert(u.size());

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

            a.push_back(0);
            b.push_back(0);
        }
    }

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

    for(auto w:to)
        pq.push({-w.second.size(),w.first});

    while(pq.size())
    {
        //cout<<pq.size()<<endl;

        pair<int, pair<int,int> > tp=pq.top();

        pq.pop();

        pair<int,int> where=tp.second;

        for(auto w:to[where])
        {
            //cout<<"w= "<<w<<endl;

            if(a[w]==0)
            {
                //cout<<"match "<<tp.first<<" "<<tp.second.first<<" "<<tp.second.second<<" with "<<w<<endl;

                a[w]=where.first;
                b[w]=where.second;

                while(from[w].size())
                {
                    set< pair<int,int> >::iterator it=from[w].begin();

                    pair<int,int> p=(*it);

                    //cout<<"p= "<<p.first<<" "<<p.second<<endl;

                    to[p].erase(w);
                    from[w].erase(p);

                    pq.push({-to[p].size(),p});
                }

                while(to[where].size())
                {
                    set< int >::iterator it=to[where].begin();

                    int p=(*it);

                    //cout<<"p= "<<p<<endl;

                    to[where].erase(p);
                    from[p].erase(where);
                }

                break;
            }
        }

        to[where]={};
    }

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

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