Submission #761486

#	Time	Username	Problem	Language	Result	Execution time	Memory
761486		caganyanmaz	Fountain Parks (IOI21_parks)	C++17	70 / 100	264 ms	63856 KiB

parks

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
int construct_roads(vector<int> x, vector<int> y);

#ifdef __DEBUG__
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b){}
#endif


constexpr static int SIZE = 200001;

vector<array<int, 3>> m;
vector<array<int, 2>> pos;
set<array<int, 2>> fountains;
bitset<SIZE> visited;
vector<int> uu, vv, aa, bb;

int get_node(int x, int y)
{
        array<int, 3> a = {x, y, 0};
        auto it = lower_bound(m.begin(), m.end(), a);
        if (it != m.end() && (*it)[0] == x && (*it)[1] == y)
                return (*it)[2];
        return -1;
}

void dfs(int node, int last, int fx, int fy);

bool try_insert(int u, int v, int fx, int fy)
{
        if (v != -1 && !visited[v] && fountains.find({fx, fy}) == fountains.end())
        {
                uu.pb(u), vv.pb(v), aa.pb(fx), bb.pb(fy);
                fountains.insert({fx, fy});
                dfs(v, u, fx, fy);
                return true;
        }
        return false;
}

// direction: 1 vertical, 0 horizontal
// orientation: 1 ccw, 0 cw
void dfs(int node, int last, int fx, int fy)
{
        visited[node] = true;
        auto [node_x, node_y] = pos[node];
        auto [last_x, last_y] = pos[last];
        int left_x = 2 * fx - last_x, left_y = 2 * fy - last_y;
        int top_x = 2 * node_x - last_x, top_y = 2 * node_y - last_y;
        int right_x = 2 * node_x - left_x, right_y = 2 * node_y - left_y;
        int left_fx = node_x + left_x - fx, left_fy = node_y + left_y - fy;
        int left = get_node(left_x, left_y), top = get_node(top_x, top_y), right = get_node(right_x, right_y);
        if (try_insert(node, left, left_fx, left_fy))
        {
                int top_fx = top_x + node_x - left_fx, top_fy = top_y + node_y - left_fy;
                int right_fx, right_fy;
                if (try_insert(node, top, top_fx, top_fy))
                        right_fx = node_x + right_x - top_fx, right_fy = node_y + right_y - top_fy;
                else
                        right_fx = top_fx, right_fy = top_fy;
                try_insert(node, right, right_fx, right_fy);
        }
        else
        {
                int right_fx = node_x * 2 - fx, right_fy = node_y * 2 - fy;
                try_insert(node, right, right_fx, right_fy);
                int top_fx = left_fx, top_fy = left_fy;
                try_insert(node, top, top_fx, top_fy);
        }
}

int construct_roads(vector<int> x, vector<int> y)
{
        for (int i = 0; i < x.size(); i++)
        {
                m.pb({x[i], y[i], i});
                pos.pb({x[i], y[i]});
        }
        sort(m.begin(), m.end());
        int a = m[0][2];
        visited[a] = true;
        int b = get_node(m[0][0], m[0][1] + 2);
        try_insert(a, b, m[0][0] - 1, m[0][1] + 1);
        int c = get_node(m[0][0] + 2, m[0][1]);
        try_insert(a, c, m[0][0] + 1, m[0][1] - 1);
        if (visited.count() == x.size())
        {
                build(uu, vv, aa, bb);
                return 1;
        }
        return 0;

}

#ifdef __DEBUG__
int main()
{
        int n;
        cin >> n;
        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++)
                cin >> x[i] >> y[i];
        if (construct_roads(x, y))
        {
                cout << "YES\n";
                for (int i = 0; i < uu.size(); i++)
                        cout << uu[i] << "-" << vv[i] << ": (" << aa[i] << ", " << bb[i] <<")\n";
        }
        else
        {
                cout << "NO\n";
        }
}

#endif

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         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