Submission #809133

#	Time	Username	Problem	Language	Result	Execution time	Memory
809133		puppy	Fountain Parks (IOI21_parks)	C++17	100 / 100	1141 ms	85024 KiB

parks

#include "parks.h"
#include <vector>
#include <map>
#include <set>
#include <functional>
using namespace std;
using pii = pair<int, int>;

struct UnionFind
{
    vector<int> par;
    UnionFind(int N)
    {
        par.resize(N+1);
        for (int i = 0; i <= N; i++) par[i] = i;
    }
    int fin(int v)
    {
        return v == par[v] ? v : (par[v] = fin(par[v]));
    }
    void uni(int u, int v)
    {
        par[fin(u)] = fin(v);
    }
    bool isuni(int u, int v)
    {
        return fin(u) == fin(v);
    }
};

int X[200005], Y[200005];
vector<int> adj[200005];
bool visited[200005];

pair<int, int> tilt(pair<int, int> ori, int pv)
{
    if (ori == make_pair(1, 0)) return make_pair(0, -pv);
    else if (ori == make_pair(0, 1)) return make_pair(pv, 0);
    else if (ori == make_pair(-1, 0)) return make_pair(0, pv);
    else return make_pair(-pv, 0);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int N = x.size();
    map<pii, int> mp;
    for (int i = 1; i <= N; i++) {
        X[i] = x[i-1], Y[i] = y[i-1];
    }
    for (int i = 1; i <= N; i++) {
        mp[make_pair(X[i], Y[i])] = i;
    }
    UnionFind uf(N);
    int dx[] = {-2, 2, 0, 0};
    int dy[] = {0, 0, -2, 2};
    for (int i = 1; i <= N; i++) {
        for (int k = 0; k < 4; k++) {
            int nx = X[i] + dx[k], ny = Y[i] + dy[k];
            int tmp = mp[make_pair(nx, ny)];
            if (tmp) {
                adj[i].push_back(tmp);
                uf.uni(i, tmp);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        if (!uf.isuni(1, i)) return 0;
    }
    vector<int> a, b, c, d;
    set<pii> st;
    int dx2[] = {1, 1, -1, -1};
    int dy2[] = {1, -1, 1, -1};
    for (int i = 1; i <= N; i++) {
        for (int k = 0; k < 4; k++) {
            st.insert(make_pair(X[i] + dx2[k], Y[i] + dy2[k]));
        }
    }
    for (pii p:st) {
        bool flag = (p.first / 2 + p.second / 2) % 2;
        int t1 = mp[{p.first - 1, p.second - 1}], t2 = flag ? mp[{p.first + 1, p.second - 1}] : mp[{p.first - 1, p.second + 1}];
        if (t1 && t2) {
            a.push_back(t1-1);
            b.push_back(t2-1);
            c.push_back(p.first);
            d.push_back(p.second);
        }
        else {
            int t3 = flag ? mp[{p.first - 1, p.second + 1}] : mp[{p.first + 1, p.second - 1}], t4 = mp[{p.first + 1, p.second + 1}];
            if (t3 && t4) {
                a.push_back(t3-1);
                b.push_back(t4-1);
                c.push_back(p.first);
                d.push_back(p.second);
            }
        }
    }
    build(a, b, c, d);
    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