oj.uz

Submission #552997

# Submission time Handle Problem Language Result Execution time Memory
552997 2022-04-24T12:21:42 Z PiejanVDC Fountain Parks (IOI21_parks) C++17
0 / 100
 3500 ms 22388 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();
    for(int A = 0 ; A < n ; 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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 215 ms 22388 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 112 ms 12300 KB Output is correct
12 Correct 28 ms 3944 KB Output is correct
13 Execution timed out 3569 ms 7908 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 215 ms 22388 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 112 ms 12300 KB Output is correct
12 Correct 28 ms 3944 KB Output is correct
13 Execution timed out 3569 ms 7908 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 215 ms 22388 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 112 ms 12300 KB Output is correct
12 Correct 28 ms 3944 KB Output is correct
13 Execution timed out 3569 ms 7908 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 215 ms 22388 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 112 ms 12300 KB Output is correct
12 Correct 28 ms 3944 KB Output is correct
13 Execution timed out 3569 ms 7908 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 215 ms 22388 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 112 ms 12300 KB Output is correct
12 Correct 28 ms 3944 KB Output is correct
13 Execution timed out 3569 ms 7908 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 215 ms 22388 KB Output is correct
10 Correct 18 ms 2644 KB Output is correct
11 Correct 112 ms 12300 KB Output is correct
12 Correct 28 ms 3944 KB Output is correct
13 Execution timed out 3569 ms 7908 KB Time limit exceeded
14 Halted 0 ms 0 KB -