oj.uz

Submission #609678

# Submission time Handle Problem Language Result Execution time Memory
609678 2022-07-27T19:13:52 Z Ozy Fountain Parks (IOI21_parks) C++17
55 / 100
 1039 ms 91248 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();
    act = {x[0],y[0]};

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

        if (nuevo < act) act = nuevo;
    }

    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 1 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 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 0 ms 212 KB Output is correct
9 Correct 395 ms 45728 KB Output is correct
10 Correct 27 ms 4968 KB Output is correct
11 Correct 188 ms 24820 KB Output is correct
12 Correct 48 ms 7352 KB Output is correct
13 Correct 112 ms 15060 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 395 ms 45728 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 0 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 0 ms 212 KB Output is correct
9 Correct 395 ms 45728 KB Output is correct
10 Correct 27 ms 4968 KB Output is correct
11 Correct 188 ms 24820 KB Output is correct
12 Correct 48 ms 7352 KB Output is correct
13 Correct 112 ms 15060 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 395 ms 45728 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 224 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 292 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 681 ms 69440 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 644 KB Output is correct
26 Correct 4 ms 980 KB Output is correct
27 Correct 3 ms 980 KB Output is correct
28 Correct 245 ms 28024 KB Output is correct
29 Correct 385 ms 41776 KB Output is correct
30 Correct 524 ms 55568 KB Output is correct
31 Correct 692 ms 69496 KB Output is correct
32 Correct 0 ms 212 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 0 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 1 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 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 724 KB Output is correct
45 Correct 353 ms 36352 KB Output is correct
46 Correct 548 ms 52752 KB Output is correct
47 Correct 546 ms 52712 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 0 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 0 ms 212 KB Output is correct
9 Correct 395 ms 45728 KB Output is correct
10 Correct 27 ms 4968 KB Output is correct
11 Correct 188 ms 24820 KB Output is correct
12 Correct 48 ms 7352 KB Output is correct
13 Correct 112 ms 15060 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 395 ms 45728 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 224 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 292 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 681 ms 69440 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 644 KB Output is correct
26 Correct 4 ms 980 KB Output is correct
27 Correct 3 ms 980 KB Output is correct
28 Correct 245 ms 28024 KB Output is correct
29 Correct 385 ms 41776 KB Output is correct
30 Correct 524 ms 55568 KB Output is correct
31 Correct 692 ms 69496 KB Output is correct
32 Correct 0 ms 212 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 0 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 1 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 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 724 KB Output is correct
45 Correct 353 ms 36352 KB Output is correct
46 Correct 548 ms 52752 KB Output is correct
47 Correct 546 ms 52712 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 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Correct 685 ms 63068 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Incorrect 5 ms 852 KB Tree @(3, 186767) appears more than once: for edges on positions 1166 and 1169
58 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 0 ms 212 KB Output is correct
9 Correct 395 ms 45728 KB Output is correct
10 Correct 27 ms 4968 KB Output is correct
11 Correct 188 ms 24820 KB Output is correct
12 Correct 48 ms 7352 KB Output is correct
13 Correct 112 ms 15060 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 395 ms 45728 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 236 KB Output is correct
20 Correct 586 ms 63556 KB Output is correct
21 Correct 647 ms 63344 KB Output is correct
22 Correct 691 ms 63320 KB Output is correct
23 Correct 659 ms 75776 KB Output is correct
24 Correct 215 ms 28356 KB Output is correct
25 Correct 218 ms 28524 KB Output is correct
26 Correct 246 ms 28556 KB Output is correct
27 Correct 707 ms 75512 KB Output is correct
28 Correct 711 ms 75532 KB Output is correct
29 Correct 988 ms 75556 KB Output is correct
30 Correct 1039 ms 75456 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 48 ms 5292 KB Output is correct
33 Correct 119 ms 14308 KB Output is correct
34 Correct 571 ms 63568 KB Output is correct
35 Correct 19 ms 2388 KB Output is correct
36 Correct 61 ms 8776 KB Output is correct
37 Correct 116 ms 15772 KB Output is correct
38 Correct 295 ms 24808 KB Output is correct
39 Correct 386 ms 33864 KB Output is correct
40 Correct 518 ms 43140 KB Output is correct
41 Correct 634 ms 52424 KB Output is correct
42 Correct 748 ms 61628 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 0 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 1 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 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 3 ms 724 KB Output is correct
55 Correct 3 ms 724 KB Output is correct
56 Correct 369 ms 36368 KB Output is correct
57 Correct 598 ms 52672 KB Output is correct
58 Correct 558 ms 52708 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 0 ms 212 KB Output is correct
62 Correct 854 ms 84976 KB Output is correct
63 Correct 799 ms 83432 KB Output is correct
64 Correct 797 ms 82232 KB Output is correct
65 Correct 6 ms 1108 KB Output is correct
66 Correct 8 ms 1680 KB Output is correct
67 Correct 362 ms 34656 KB Output is correct
68 Correct 588 ms 51872 KB Output is correct
69 Correct 848 ms 69184 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 0 ms 212 KB Output is correct
9 Correct 395 ms 45728 KB Output is correct
10 Correct 27 ms 4968 KB Output is correct
11 Correct 188 ms 24820 KB Output is correct
12 Correct 48 ms 7352 KB Output is correct
13 Correct 112 ms 15060 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 395 ms 45728 KB Output is correct
17 Correct 898 ms 91248 KB Output is correct
18 Correct 790 ms 90524 KB Output is correct
19 Correct 660 ms 63288 KB Output is correct
20 Correct 762 ms 59868 KB Output is correct
21 Correct 768 ms 69084 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 98 ms 11108 KB Output is correct
24 Correct 36 ms 4340 KB Output is correct
25 Correct 106 ms 11604 KB Output is correct
26 Correct 143 ms 18716 KB Output is correct
27 Correct 363 ms 30452 KB Output is correct
28 Correct 462 ms 38104 KB Output is correct
29 Correct 588 ms 45804 KB Output is correct
30 Correct 663 ms 53004 KB Output is correct
31 Correct 828 ms 60848 KB Output is correct
32 Correct 804 ms 71844 KB Output is correct
33 Correct 839 ms 85112 KB Output is correct
34 Correct 8 ms 1364 KB Output is correct
35 Correct 9 ms 1820 KB Output is correct
36 Correct 410 ms 34672 KB Output is correct
37 Correct 567 ms 51896 KB Output is correct
38 Correct 758 ms 69092 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 0 ms 212 KB Output is correct
9 Correct 395 ms 45728 KB Output is correct
10 Correct 27 ms 4968 KB Output is correct
11 Correct 188 ms 24820 KB Output is correct
12 Correct 48 ms 7352 KB Output is correct
13 Correct 112 ms 15060 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 395 ms 45728 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 224 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 292 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 681 ms 69440 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 644 KB Output is correct
26 Correct 4 ms 980 KB Output is correct
27 Correct 3 ms 980 KB Output is correct
28 Correct 245 ms 28024 KB Output is correct
29 Correct 385 ms 41776 KB Output is correct
30 Correct 524 ms 55568 KB Output is correct
31 Correct 692 ms 69496 KB Output is correct
32 Correct 0 ms 212 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 0 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 1 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 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 724 KB Output is correct
45 Correct 353 ms 36352 KB Output is correct
46 Correct 548 ms 52752 KB Output is correct
47 Correct 546 ms 52712 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 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Correct 685 ms 63068 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Incorrect 5 ms 852 KB Tree @(3, 186767) appears more than once: for edges on positions 1166 and 1169
58 Halted 0 ms 0 KB -