oj.uz

Submission #609668

# Submission time Handle Problem Language Result Execution time Memory
609668 2022-07-27T19:03:24 Z Ozy Fountain Parks (IOI21_parks) C++17
55 / 100
 1101 ms 91244 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 361 ms 44392 KB Output is correct
10 Correct 28 ms 4948 KB Output is correct
11 Correct 189 ms 24904 KB Output is correct
12 Correct 54 ms 7356 KB Output is correct
13 Correct 110 ms 15032 KB Output is correct
14 Correct 2 ms 496 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 388 ms 45144 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 361 ms 44392 KB Output is correct
10 Correct 28 ms 4948 KB Output is correct
11 Correct 189 ms 24904 KB Output is correct
12 Correct 54 ms 7356 KB Output is correct
13 Correct 110 ms 15032 KB Output is correct
14 Correct 2 ms 496 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 388 ms 45144 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 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 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1042 ms 66972 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 5 ms 948 KB Output is correct
27 Correct 6 ms 980 KB Output is correct
28 Correct 365 ms 29112 KB Output is correct
29 Correct 460 ms 42100 KB Output is correct
30 Correct 705 ms 55752 KB Output is correct
31 Correct 869 ms 67528 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 292 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 5 ms 724 KB Output is correct
44 Correct 4 ms 852 KB Output is correct
45 Correct 448 ms 36352 KB Output is correct
46 Correct 745 ms 52588 KB Output is correct
47 Correct 701 ms 52716 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 361 ms 44392 KB Output is correct
10 Correct 28 ms 4948 KB Output is correct
11 Correct 189 ms 24904 KB Output is correct
12 Correct 54 ms 7356 KB Output is correct
13 Correct 110 ms 15032 KB Output is correct
14 Correct 2 ms 496 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 388 ms 45144 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 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 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1042 ms 66972 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 5 ms 948 KB Output is correct
27 Correct 6 ms 980 KB Output is correct
28 Correct 365 ms 29112 KB Output is correct
29 Correct 460 ms 42100 KB Output is correct
30 Correct 705 ms 55752 KB Output is correct
31 Correct 869 ms 67528 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 292 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 5 ms 724 KB Output is correct
44 Correct 4 ms 852 KB Output is correct
45 Correct 448 ms 36352 KB Output is correct
46 Correct 745 ms 52588 KB Output is correct
47 Correct 701 ms 52716 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 0 ms 212 KB Output is correct
55 Correct 853 ms 63628 KB Output is correct
56 Correct 0 ms 212 KB Output is correct
57 Incorrect 6 ms 820 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 361 ms 44392 KB Output is correct
10 Correct 28 ms 4948 KB Output is correct
11 Correct 189 ms 24904 KB Output is correct
12 Correct 54 ms 7356 KB Output is correct
13 Correct 110 ms 15032 KB Output is correct
14 Correct 2 ms 496 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 388 ms 45144 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 889 ms 66576 KB Output is correct
21 Correct 799 ms 64180 KB Output is correct
22 Correct 743 ms 64272 KB Output is correct
23 Correct 772 ms 76584 KB Output is correct
24 Correct 288 ms 28552 KB Output is correct
25 Correct 237 ms 28584 KB Output is correct
26 Correct 238 ms 28564 KB Output is correct
27 Correct 774 ms 75476 KB Output is correct
28 Correct 785 ms 75428 KB Output is correct
29 Correct 1074 ms 75488 KB Output is correct
30 Correct 1101 ms 75492 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 63 ms 5248 KB Output is correct
33 Correct 108 ms 14328 KB Output is correct
34 Correct 635 ms 64096 KB Output is correct
35 Correct 18 ms 2292 KB Output is correct
36 Correct 68 ms 8760 KB Output is correct
37 Correct 115 ms 15728 KB Output is correct
38 Correct 418 ms 24804 KB Output is correct
39 Correct 412 ms 33956 KB Output is correct
40 Correct 563 ms 43296 KB Output is correct
41 Correct 707 ms 52496 KB Output is correct
42 Correct 898 ms 61708 KB Output is correct
43 Correct 0 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 212 KB Output is correct
47 Correct 0 ms 212 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 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 0 ms 212 KB Output is correct
54 Correct 3 ms 724 KB Output is correct
55 Correct 3 ms 724 KB Output is correct
56 Correct 423 ms 36368 KB Output is correct
57 Correct 551 ms 52668 KB Output is correct
58 Correct 562 ms 52644 KB Output is correct
59 Correct 0 ms 212 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 1 ms 212 KB Output is correct
62 Correct 786 ms 82880 KB Output is correct
63 Correct 757 ms 84140 KB Output is correct
64 Correct 783 ms 84108 KB Output is correct
65 Correct 6 ms 1108 KB Output is correct
66 Correct 9 ms 1720 KB Output is correct
67 Correct 398 ms 34696 KB Output is correct
68 Correct 611 ms 51892 KB Output is correct
69 Correct 805 ms 69068 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 361 ms 44392 KB Output is correct
10 Correct 28 ms 4948 KB Output is correct
11 Correct 189 ms 24904 KB Output is correct
12 Correct 54 ms 7356 KB Output is correct
13 Correct 110 ms 15032 KB Output is correct
14 Correct 2 ms 496 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 388 ms 45144 KB Output is correct
17 Correct 804 ms 91244 KB Output is correct
18 Correct 798 ms 90176 KB Output is correct
19 Correct 645 ms 63484 KB Output is correct
20 Correct 645 ms 59892 KB Output is correct
21 Correct 769 ms 69100 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 103 ms 11068 KB Output is correct
24 Correct 35 ms 4444 KB Output is correct
25 Correct 88 ms 11708 KB Output is correct
26 Correct 150 ms 18708 KB Output is correct
27 Correct 386 ms 30472 KB Output is correct
28 Correct 495 ms 38124 KB Output is correct
29 Correct 607 ms 45824 KB Output is correct
30 Correct 701 ms 52932 KB Output is correct
31 Correct 835 ms 60916 KB Output is correct
32 Correct 752 ms 71832 KB Output is correct
33 Correct 803 ms 85004 KB Output is correct
34 Correct 8 ms 1364 KB Output is correct
35 Correct 14 ms 2132 KB Output is correct
36 Correct 392 ms 34656 KB Output is correct
37 Correct 565 ms 51900 KB Output is correct
38 Correct 760 ms 69120 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 361 ms 44392 KB Output is correct
10 Correct 28 ms 4948 KB Output is correct
11 Correct 189 ms 24904 KB Output is correct
12 Correct 54 ms 7356 KB Output is correct
13 Correct 110 ms 15032 KB Output is correct
14 Correct 2 ms 496 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 388 ms 45144 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 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 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1042 ms 66972 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 4 ms 724 KB Output is correct
26 Correct 5 ms 948 KB Output is correct
27 Correct 6 ms 980 KB Output is correct
28 Correct 365 ms 29112 KB Output is correct
29 Correct 460 ms 42100 KB Output is correct
30 Correct 705 ms 55752 KB Output is correct
31 Correct 869 ms 67528 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 292 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 5 ms 724 KB Output is correct
44 Correct 4 ms 852 KB Output is correct
45 Correct 448 ms 36352 KB Output is correct
46 Correct 745 ms 52588 KB Output is correct
47 Correct 701 ms 52716 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 0 ms 212 KB Output is correct
55 Correct 853 ms 63628 KB Output is correct
56 Correct 0 ms 212 KB Output is correct
57 Incorrect 6 ms 820 KB Tree @(3, 186767) appears more than once: for edges on positions 238 and 241
58 Halted 0 ms 0 KB -