Submission #553877

#	Time	Username	Problem	Language	Result	Execution time	Memory
553877		topovik	Fountain Parks (IOI21_parks)	C++17	100 / 100	1605 ms	93340 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
#define pb push_back
#define f first
#define s second
#define pi acos(-1)

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e9;
const ld eps = (ld)1 / oo;
const ll N = 2e5 + 100;
const ll M = 1e6;

const int step[4][2] = {{0, -2}, {0, 2}, {-2, 0}, {2, 0}};

vector <pair<int, int> > ans;
map <int, int> mp[N];
map <int, pair<int, int> > mp1[N];
int pred[N];

//void build(vector <int> u, vector <int> v, vector <int> a, vector <int> b)
//{
//    for (int i = 0; i < u.size(); i++) cout << u[i] << " " << v[i] << " " << a[i] << " " << b[i] << endl;
//}

int get(int x)
{
    return ((pred[x] == x) ? x : (pred[x] = get(pred[x])));
}

void unite(int x, int y)
{
     pred[x] = y;
}

int construct_roads (vector<int> x, vector<int> y) {
    std::vector<int> u, v, a, b;
    int n = x.size();
    set <pair<int, int> > st;
    for (int i = 0; i < n; i++) mp[x[i]][y[i]] = i + 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int x1 = x[i] + step[j][0];
            int y1 = y[i] + step[j][1];
            if (mp[x1][y1] != 0)
            {
                int x2 = (x[i] + x1) / 2;
                int y2 = (y[i] + y1) / 2;
                mp1[x2][y2] = {i + 1, mp[x1][y1]};
                for (int c = 0; c < 4; c++)
                {
                    int x3 = x2 + step[c][0] / 2;
                    int y3 = y2 + step[c][1] / 2;
                    if ((x3 & 1) && (y3 & 1)) st.insert({x3, y3});
                }
            }
        }
    }
    for (int i = 0; i < n; i++) pred[i] = i;
    int kol = n - 1;
    while (!st.empty())
    {
        pair<int, int> c = *st.begin();
        st.erase(st.begin());
        int x = c.f, y = c.s;
        for (int i = (((x + y) / 2) & 1) * 2; i <  (((x + y) / 2) & 1) * 2 + 2; i++)
        {
            int x1 = x + step[i][0] / 2;
            int y1 = y + step[i][1] / 2;
            if (mp1[x1].find(y1) != mp1[x1].end())
            {
                c = mp1[x1][y1];
                c.f--, c.s--;
                if (get(c.f) != get(c.s))
                {
                    unite(get(c.f), get(c.s));
                    u.pb(c.f);
                    v.pb(c.s);
                    a.pb(x);
                    b.pb(y);
                    kol--;
                    break;
                }
            }
        }
    }
    if (kol == 0)
    {
        build(u, v, a, b);
        return 1;
    }
    return 0;
}

//int main()
//{
//    int n;
//    cin >> n;
//    vector <int> x(n), y(n);
//    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
//    cout << construct_roads(x, y) << endl;
//}
/*
1
4
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
*/

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