Submission #553001

#	Time	Username	Problem	Language	Result	Execution time	Memory
553001		PiejanVDC	Fountain Parks (IOI21_parks)	C++17	15 / 100	1485 ms	45240 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;

int dx[4] = {2,0,-2,0};
int dy[4] = {0,2,0,-2};

struct S {
    int x,y;
    int dir;
}s_;

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

const int mxN = (int)2e5 + 5;

int construct_roads(std::vector<int> x, std::vector<int> y) {
    const int n = (int)x.size();
    for(int A = 0 ; A < min(n, 10) ; A++) {
        map<pair<int,int>,int>mp;
        for(int i = 0 ; i < n ; i++)
            mp[{x[i],y[i]}] = i;
        vector<int>u(n-1),v(n-1),a(n-1),b(n-1);
        set<pair<int,int>>processed;

        stack<S>s;

        s_.x = x[A], s_.y = y[A], s_.dir = 0;
        processed.insert({x[A], y[A]});
        s.push(s_);

        int P = 0;
        while(!s.empty()) {
            auto node = s.top();
            s.pop();

            int x = node.x, y = node.y, dir = node.dir;
            bool in_order = 0;

            if(mp.count({x + dx[dir], y + dy[dir]})) in_order = 1;

            int i = dir;
            int ii = mp[{x,y}];

            int p_ = P;

            if(!in_order) {
                dir--;
                i--;
                dir += 4;
                i += 4;
                dir %= 4;
                i %= 4;
            } else {
                dir++;
                i++;
                dir += 4;
                i += 4;
                dir %= 4;
                i %= 4;
            }

            do {
                if(in_order) {
                    if(mp.count({x + dx[i], y + dy[i]}) && !processed.count({x + dx[i], y + dy[i]})) {
                        if(dx[i] == 0 && dy[i] == 2) {
                            if(!processed.count({x+1,y + dy[i]/2}))
                                a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x-1,y + dy[i]/2}))
                                a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        } else if(dx[i] == 0 && dy[i] == -2) {
                            if(!processed.count({x-1,y + dy[i]/2}))
                                a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x+1,y + dy[i]/2}))
                                a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        } else if(dy[i] == 0 && dx[i] == 2) {
                            if(!processed.count({x + dx[i]/2, y-1}))
                                a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x + dx[i]/2, y+1}))
                                a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        } else if(dy[i] == 0 && dx[i] == -2) {
                            if(!processed.count({x + dx[i]/2, y+1}))
                                a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x + dx[i]/2, y-1}))
                                a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        }
                    }
                } else {
                    if(mp.count({x + dx[i], y + dy[i]}) && !processed.count({x + dx[i], y + dy[i]})) {
                        if(dx[i] == 0 && dy[i] == 2) {
                            if(!processed.count({x-1,y + dy[i]/2}))
                                a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x+1,y + dy[i]/2}))
                                a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        } else if(dx[i] == 0 && dy[i] == -2) {
                            if(!processed.count({x+1,y + dy[i]/2}))
                                a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x-1,y + dy[i]/2}))
                                a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        } else if(dy[i] == 0 && dx[i] == 2) {
                            if(!processed.count({x + dx[i]/2, y+1}))
                                a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x + dx[i]/2, y-1}))
                                a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        } else if(dy[i] == 0 && dx[i] == -2) {
                            if(!processed.count({x + dx[i]/2, y-1}))
                                a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                            else if(!processed.count({x + dx[i]/2, y+1}))
                                a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
                        }
                    }
                }
                if(in_order) i++,i%=4;
                else i--, i+=4, i%= 4;
            } while(i != dir);

        }

        if(P < n-1)
            continue;

        build(u,v,a,b);
        return 1;
    }
    return 0;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:45:17: warning: unused variable 'p_' [-Wunused-variable]
   45 |             int p_ = P;
      |                 ^~

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