oj.uz

Submission #552866

# Submission time Handle Problem Language Result Execution time Memory
552866 2022-04-24T08:15:15 Z PiejanVDC Fountain Parks (IOI21_parks) C++17
15 / 100
 671 ms 46904 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(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++;
                    }
                }
            }
            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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 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 1 ms 304 KB Output is correct
9 Correct 256 ms 22984 KB Output is correct
10 Correct 20 ms 2588 KB Output is correct
11 Correct 120 ms 12548 KB Output is correct
12 Correct 30 ms 3928 KB Output is correct
13 Correct 63 ms 7628 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 222 ms 23188 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 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 1 ms 304 KB Output is correct
9 Correct 256 ms 22984 KB Output is correct
10 Correct 20 ms 2588 KB Output is correct
11 Correct 120 ms 12548 KB Output is correct
12 Correct 30 ms 3928 KB Output is correct
13 Correct 63 ms 7628 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 222 ms 23188 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 280 KB Output is correct
19 Correct 2 ms 212 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 590 ms 46904 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 560 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 3 ms 748 KB Output is correct
28 Correct 230 ms 18956 KB Output is correct
29 Correct 286 ms 27860 KB Output is correct
30 Correct 445 ms 36820 KB Output is correct
31 Correct 519 ms 46792 KB Output is correct
32 Correct 1 ms 296 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 300 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 300 KB Output is correct
41 Correct 1 ms 296 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 2 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 232 ms 23224 KB Output is correct
46 Correct 411 ms 33360 KB Output is correct
47 Correct 415 ms 33352 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 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 1 ms 304 KB Output is correct
9 Correct 256 ms 22984 KB Output is correct
10 Correct 20 ms 2588 KB Output is correct
11 Correct 120 ms 12548 KB Output is correct
12 Correct 30 ms 3928 KB Output is correct
13 Correct 63 ms 7628 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 222 ms 23188 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 280 KB Output is correct
19 Correct 2 ms 212 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 590 ms 46904 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 560 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 3 ms 748 KB Output is correct
28 Correct 230 ms 18956 KB Output is correct
29 Correct 286 ms 27860 KB Output is correct
30 Correct 445 ms 36820 KB Output is correct
31 Correct 519 ms 46792 KB Output is correct
32 Correct 1 ms 296 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 300 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 300 KB Output is correct
41 Correct 1 ms 296 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 2 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 232 ms 23224 KB Output is correct
46 Correct 411 ms 33360 KB Output is correct
47 Correct 415 ms 33352 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 296 KB Output is correct
55 Correct 589 ms 46580 KB Output is correct
56 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
57 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 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 1 ms 304 KB Output is correct
9 Correct 256 ms 22984 KB Output is correct
10 Correct 20 ms 2588 KB Output is correct
11 Correct 120 ms 12548 KB Output is correct
12 Correct 30 ms 3928 KB Output is correct
13 Correct 63 ms 7628 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 222 ms 23188 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 597 ms 46616 KB Output is correct
21 Correct 605 ms 46468 KB Output is correct
22 Correct 580 ms 46328 KB Output is correct
23 Correct 486 ms 39344 KB Output is correct
24 Correct 194 ms 20796 KB Output is correct
25 Correct 163 ms 20676 KB Output is correct
26 Correct 189 ms 20668 KB Output is correct
27 Correct 453 ms 45776 KB Output is correct
28 Correct 481 ms 45696 KB Output is correct
29 Correct 632 ms 45780 KB Output is correct
30 Correct 585 ms 45648 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 8 ms 1740 KB Solution announced impossible, but it is possible.
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 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 1 ms 304 KB Output is correct
9 Correct 256 ms 22984 KB Output is correct
10 Correct 20 ms 2588 KB Output is correct
11 Correct 120 ms 12548 KB Output is correct
12 Correct 30 ms 3928 KB Output is correct
13 Correct 63 ms 7628 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 222 ms 23188 KB Output is correct
17 Correct 519 ms 46188 KB Output is correct
18 Correct 488 ms 46312 KB Output is correct
19 Correct 526 ms 46412 KB Output is correct
20 Correct 671 ms 45456 KB Output is correct
21 Correct 493 ms 40224 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 47 ms 5380 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 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 1 ms 304 KB Output is correct
9 Correct 256 ms 22984 KB Output is correct
10 Correct 20 ms 2588 KB Output is correct
11 Correct 120 ms 12548 KB Output is correct
12 Correct 30 ms 3928 KB Output is correct
13 Correct 63 ms 7628 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 222 ms 23188 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 280 KB Output is correct
19 Correct 2 ms 212 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 590 ms 46904 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 560 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 3 ms 748 KB Output is correct
28 Correct 230 ms 18956 KB Output is correct
29 Correct 286 ms 27860 KB Output is correct
30 Correct 445 ms 36820 KB Output is correct
31 Correct 519 ms 46792 KB Output is correct
32 Correct 1 ms 296 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 300 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 300 KB Output is correct
41 Correct 1 ms 296 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 2 ms 596 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 232 ms 23224 KB Output is correct
46 Correct 411 ms 33360 KB Output is correct
47 Correct 415 ms 33352 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 296 KB Output is correct
55 Correct 589 ms 46580 KB Output is correct
56 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
57 Halted 0 ms 0 KB -