Submission #1070960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070960		jerzyk	Fountain Parks (IOI21_parks)	C++17	100 / 100	270 ms	44556 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int fau[N];
pair<int, int> tab[N], ntab[N];
map<pair<int, int>, int> pts;
vector<pair<int, int>> ed;
vector<pair<int, int>> ben;
vector<int> ans1, ans2, ans3, ans4;

int Find(int v)
{
    return (fau[v] = (fau[v] == v ? v : Find(fau[v])));
}

void Union(int a, int b)
{
    fau[Find(b)] = Find(a);
}

int Check(int x, int y)
{
    if(pts.find(make_pair(x, y)) != pts.end())
        return pts[make_pair(x, y)];
    return -1;
}

bool Clr(pair<int, int> a)
{
    return (((a.st + a.nd) / 2) % 2 == 0);
}

void MakE(int n)
{
    for(int i = 0; i < n; ++i)
    {
        int v = Check(ntab[i].st, ntab[i].nd);
        int u = Check(ntab[i].st, ntab[i].nd + 2), l = Check(ntab[i].st - 2, ntab[i].nd);
        if(u != -1 && l != -1 && Check(ntab[i].st - 2, ntab[i].nd + 2) != -1)
        {
            //cerr << "XDKURAWdasljlsdfkjakd\n";
            if(Clr(ntab[i])) ed.pb(make_pair(v, u));
            else ed.pb(make_pair(v, l));
            continue;
        }
        if(u != -1)
            ed.pb(make_pair(v, u));
        if(l != -1)
            ed.pb(make_pair(v, l));
    }
}

void SpTree()
{
    vector<pair<int, int>> nxt;
    for(int i = 0; i < (int)ed.size(); ++i)
    {
        //cerr << ed[i].st << " " << ed[i].nd << "\n";
        if(Find(ed[i].st) != Find(ed[i].nd))
        {
            Union(ed[i].st, ed[i].nd);
            nxt.pb(ed[i]);
        }
    }
    ed = nxt;
}

void DoB()
{
    for(int i = 0; i < (int)ed.size(); ++i)
    {
        int v = ed[i].st, u = ed[i].nd;
        //cerr << "ed: " << Clr(tab[v]) << "\n";
        if(tab[u].st == tab[v].st)
        {
            if(Clr(tab[v]))
                ben.pb(make_pair(tab[v].st + 1, tab[v].nd + 1));
            else
                ben.pb(make_pair(tab[v].st - 1, tab[v].nd + 1));
        }else
        {
            if(Clr(tab[v]))
                ben.pb(make_pair(tab[v].st - 1, tab[v].nd + 1));
            else
                ben.pb(make_pair(tab[v].st - 1, tab[v].nd - 1));
        }
    }
}

void ConstructAnswer()
{
    for(int i = 0; i < (int)ed.size(); ++i)
    {
        ans1.pb(ed[i].st); ans2.pb(ed[i].nd);
        ans3.pb(ben[i].st); ans4.pb(ben[i].nd);
    }
}

int construct_roads(vector<int> _x, vector<int> _y)
{
    int n = _x.size();
    //cerr << "Input " << "\n";
    for(int i = 0; i < n; ++i)
    {
        tab[i] = make_pair(_x[i], _y[i]);
        //cerr << i << " " << tab[i].st << " " << tab[i].nd << "\n";
        pts[tab[i]] = i;
        fau[i] = i;
        ntab[i] = tab[i];
    }
    sort(ntab, ntab + n);
    MakE(n);
    //cerr << "xd\n";
    SpTree();
    //cerr << "xd\n";
    if((int)ed.size() < n - 1) return 0;
    DoB();
    ConstructAnswer();
    build(ans1, ans2, ans3, ans4);
    return 1;
}

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