Submission #809082

#	Time	Username	Problem	Language	Result	Execution time	Memory
809082		puppy	Fountain Parks (IOI21_parks)	C++17	45 / 100	712 ms	85968 KiB

parks

#include "parks.h"
#include <vector>
#include <map>
#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;
    function<void(int, int)> dfs = [&](int v, int depth)
    {
        visited[v] = true;
        for (int i:adj[v]) {
            if (visited[i]) continue;
            int mx = X[v] + X[i] >> 1, my = Y[v] + Y[i] >> 1;
            pair<int, int> ori = make_pair((X[i] - X[v]) / 2, (Y[i] - Y[v]) / 2);
            pair<int, int> nxt = tilt(ori, (depth % 2) * 2 - 1);
            a.push_back(v-1);
            b.push_back(i-1);
            c.push_back(mx + nxt.first);
            d.push_back(my + nxt.second);
            dfs(i, depth + 1);
        }
    };
    dfs(1, 0);
    build(a, b, c, d);
    return 1;
}

Compilation message (stderr)

parks.cpp: In lambda function:
parks.cpp:73:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |             int mx = X[v] + X[i] >> 1, my = Y[v] + Y[i] >> 1;
      |                      ~~~~~^~~~~~
parks.cpp:73:50: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |             int mx = X[v] + X[i] >> 1, my = Y[v] + Y[i] >> 1;
      |                                             ~~~~~^~~~~~

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