oj.uz

Submission #609656

# Submission time Handle Problem Language Result Execution time Memory
609656 2022-07-27T18:54:04 Z Ozy Fountain Parks (IOI21_parks) C++17
55 / 100
 1164 ms 93292 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define X first
#define Y second

map<pair<int,int>, int> mapa,id,bancas;
lli n,p;
stack<pair<lli,lli> > pila;
pair<lli,lli> act,nuevo,mitad;

vector<int> u,v,a,b;
lli dir[8] = {0,2,0,-2,2,0,-2,0};
bool continua;

void construye(int U, int V, int A, int B) {

    u.push_back(U);
    v.push_back(V);
    a.push_back(A);
    b.push_back(B);
}

//quitar varios logs si no da en tiempo
int construct_roads(std::vector<int> x, std::vector<int> y) {

    n = x.size();
    rep(i,0,n-1) {
        mapa[{x[i],y[i]}] = 1;
        id[{x[i],y[i]}] = i;
    }

    act = {x[0],y[0]};
    pila.push(act);
    while (!pila.empty()) {

        act = pila.top();
        mapa[act] = 2;
        continua = false;

        rep(i,0,3){
            nuevo = act;
            nuevo.X += dir[i];
            nuevo.Y += dir[i+4];

            p = mapa[nuevo];
            if (p == 0 || p == 2) continue;

            mitad.X = (act.X + nuevo.X)/2;
            mitad.Y = (act.Y + nuevo.Y)/2;

            if (i&1) {
                //movimiento horizontal
                mitad.Y++;
                if (bancas[mitad] == 1) {
                    mitad.Y -= 2;
                    construye(id[act], id[nuevo], mitad.X, mitad.Y);
                    bancas[mitad] = 1;
                    pila.push(nuevo);
                    continua=true;
                    break;
                }

                mitad.Y -= 2;
                if (bancas[mitad] == 1) {
                    mitad.Y += 2;
                    construye(id[act], id[nuevo], mitad.X, mitad.Y);
                    bancas[mitad] = 1;
                    pila.push(nuevo);
                    continua=true;
                    break;
                }
            }
            else {
                //movimiento vertical
                mitad.X++;
                if (bancas[mitad] == 1) {
                    mitad.X -= 2;
                    construye(id[act], id[nuevo], mitad.X, mitad.Y);
                    bancas[mitad] = 1;
                    pila.push(nuevo);
                    continua=true;
                    break;
                }

                mitad.X -= 2;
                if (bancas[mitad] == 1) {
                    mitad.X += 2;
                    construye(id[act], id[nuevo], mitad.X, mitad.Y);
                    bancas[mitad] = 1;
                    pila.push(nuevo);
                    continua=true;
                    break;
                }
            }
        }

        if (continua) {
            n--;
            continue;
        }
        rep(i,0,3) {
            nuevo = act;
            nuevo.X += dir[i];
            nuevo.Y += dir[i+4];

            p = mapa[nuevo];
            if (p == 0 || p == 2) continue;

            mitad.X = (act.X + nuevo.X)/2;
            mitad.Y = (act.Y + nuevo.Y)/2;
            if (i&1) mitad.Y++;
            else mitad.X++;


            construye(id[act], id[nuevo], mitad.X, mitad.Y);
            bancas[mitad] = 1;
            pila.push(nuevo);
            continua=true;
            break;
        }

        if (continua) {
            n--;
            continue;
        }
        pila.pop();
    }

    if (n > 1) return 0;

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 357 ms 45148 KB Output is correct
10 Correct 28 ms 5068 KB Output is correct
11 Correct 186 ms 25160 KB Output is correct
12 Correct 43 ms 7424 KB Output is correct
13 Correct 101 ms 15472 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 399 ms 45804 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 357 ms 45148 KB Output is correct
10 Correct 28 ms 5068 KB Output is correct
11 Correct 186 ms 25160 KB Output is correct
12 Correct 43 ms 7424 KB Output is correct
13 Correct 101 ms 15472 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 399 ms 45804 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 709 ms 68544 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 4 ms 688 KB Output is correct
26 Correct 7 ms 980 KB Output is correct
27 Correct 4 ms 952 KB Output is correct
28 Correct 285 ms 29728 KB Output is correct
29 Correct 401 ms 43224 KB Output is correct
30 Correct 538 ms 56996 KB Output is correct
31 Correct 700 ms 69156 KB Output is correct
32 Correct 0 ms 300 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 3 ms 724 KB Output is correct
44 Correct 3 ms 804 KB Output is correct
45 Correct 360 ms 37168 KB Output is correct
46 Correct 534 ms 53860 KB Output is correct
47 Correct 535 ms 53872 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 357 ms 45148 KB Output is correct
10 Correct 28 ms 5068 KB Output is correct
11 Correct 186 ms 25160 KB Output is correct
12 Correct 43 ms 7424 KB Output is correct
13 Correct 101 ms 15472 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 399 ms 45804 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 709 ms 68544 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 4 ms 688 KB Output is correct
26 Correct 7 ms 980 KB Output is correct
27 Correct 4 ms 952 KB Output is correct
28 Correct 285 ms 29728 KB Output is correct
29 Correct 401 ms 43224 KB Output is correct
30 Correct 538 ms 56996 KB Output is correct
31 Correct 700 ms 69156 KB Output is correct
32 Correct 0 ms 300 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 3 ms 724 KB Output is correct
44 Correct 3 ms 804 KB Output is correct
45 Correct 360 ms 37168 KB Output is correct
46 Correct 534 ms 53860 KB Output is correct
47 Correct 535 ms 53872 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 300 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 300 KB Output is correct
55 Correct 689 ms 66780 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Incorrect 4 ms 852 KB Tree @(3, 186767) appears more than once: for edges on positions 238 and 241
58 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 357 ms 45148 KB Output is correct
10 Correct 28 ms 5068 KB Output is correct
11 Correct 186 ms 25160 KB Output is correct
12 Correct 43 ms 7424 KB Output is correct
13 Correct 101 ms 15472 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 399 ms 45804 KB Output is correct
17 Correct 0 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 604 ms 66096 KB Output is correct
21 Correct 626 ms 66468 KB Output is correct
22 Correct 624 ms 65644 KB Output is correct
23 Correct 659 ms 78412 KB Output is correct
24 Correct 214 ms 30276 KB Output is correct
25 Correct 212 ms 30196 KB Output is correct
26 Correct 218 ms 30120 KB Output is correct
27 Correct 714 ms 77060 KB Output is correct
28 Correct 738 ms 77244 KB Output is correct
29 Correct 1136 ms 77036 KB Output is correct
30 Correct 1164 ms 77036 KB Output is correct
31 Correct 1 ms 256 KB Output is correct
32 Correct 54 ms 5424 KB Output is correct
33 Correct 114 ms 15568 KB Output is correct
34 Correct 633 ms 66608 KB Output is correct
35 Correct 19 ms 2460 KB Output is correct
36 Correct 76 ms 9308 KB Output is correct
37 Correct 119 ms 17076 KB Output is correct
38 Correct 297 ms 25904 KB Output is correct
39 Correct 402 ms 35324 KB Output is correct
40 Correct 574 ms 45000 KB Output is correct
41 Correct 644 ms 54612 KB Output is correct
42 Correct 833 ms 64160 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 0 ms 304 KB Output is correct
47 Correct 0 ms 212 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 5 ms 724 KB Output is correct
55 Correct 4 ms 852 KB Output is correct
56 Correct 402 ms 37308 KB Output is correct
57 Correct 596 ms 53808 KB Output is correct
58 Correct 757 ms 53844 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 1 ms 212 KB Output is correct
62 Correct 791 ms 84552 KB Output is correct
63 Correct 780 ms 85804 KB Output is correct
64 Correct 803 ms 85660 KB Output is correct
65 Correct 6 ms 1236 KB Output is correct
66 Correct 11 ms 1836 KB Output is correct
67 Correct 358 ms 35588 KB Output is correct
68 Correct 558 ms 53116 KB Output is correct
69 Correct 761 ms 70772 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 357 ms 45148 KB Output is correct
10 Correct 28 ms 5068 KB Output is correct
11 Correct 186 ms 25160 KB Output is correct
12 Correct 43 ms 7424 KB Output is correct
13 Correct 101 ms 15472 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 399 ms 45804 KB Output is correct
17 Correct 799 ms 93292 KB Output is correct
18 Correct 774 ms 92096 KB Output is correct
19 Correct 653 ms 65768 KB Output is correct
20 Correct 714 ms 61364 KB Output is correct
21 Correct 696 ms 70472 KB Output is correct
22 Correct 0 ms 296 KB Output is correct
23 Correct 105 ms 11404 KB Output is correct
24 Correct 35 ms 4656 KB Output is correct
25 Correct 90 ms 12708 KB Output is correct
26 Correct 141 ms 20176 KB Output is correct
27 Correct 350 ms 31700 KB Output is correct
28 Correct 458 ms 39756 KB Output is correct
29 Correct 578 ms 47724 KB Output is correct
30 Correct 678 ms 55064 KB Output is correct
31 Correct 768 ms 63256 KB Output is correct
32 Correct 729 ms 72480 KB Output is correct
33 Correct 761 ms 86780 KB Output is correct
34 Correct 7 ms 1400 KB Output is correct
35 Correct 13 ms 2260 KB Output is correct
36 Correct 354 ms 35468 KB Output is correct
37 Correct 551 ms 53148 KB Output is correct
38 Correct 741 ms 70820 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 357 ms 45148 KB Output is correct
10 Correct 28 ms 5068 KB Output is correct
11 Correct 186 ms 25160 KB Output is correct
12 Correct 43 ms 7424 KB Output is correct
13 Correct 101 ms 15472 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 399 ms 45804 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 709 ms 68544 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 4 ms 688 KB Output is correct
26 Correct 7 ms 980 KB Output is correct
27 Correct 4 ms 952 KB Output is correct
28 Correct 285 ms 29728 KB Output is correct
29 Correct 401 ms 43224 KB Output is correct
30 Correct 538 ms 56996 KB Output is correct
31 Correct 700 ms 69156 KB Output is correct
32 Correct 0 ms 300 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 3 ms 724 KB Output is correct
44 Correct 3 ms 804 KB Output is correct
45 Correct 360 ms 37168 KB Output is correct
46 Correct 534 ms 53860 KB Output is correct
47 Correct 535 ms 53872 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 300 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 300 KB Output is correct
55 Correct 689 ms 66780 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Incorrect 4 ms 852 KB Tree @(3, 186767) appears more than once: for edges on positions 238 and 241
58 Halted 0 ms 0 KB -