oj.uz

Submission #552864

# Submission time Handle Problem Language Result Execution time Memory
552864 2022-04-24T08:14:00 Z PiejanVDC Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 340 KB 
#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();
    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[0], s_.y = y[0], s_.dir = 0;
    processed.insert({x[0], y[0]});
    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) {
                    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(!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(dx[i] == 0) {
                    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(!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)
        return 0;

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

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -