oj.uz

Submission #1062265

# Submission time Handle Problem Language Result Execution time Memory
1062265 2024-08-16T23:08:21 Z mariaclara Fountain Parks (IOI21_parks) C++17
15 / 100
 409 ms 88488 KB 
#include "parks.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAX = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int N;
vector<int> v[MAX], X, Y;
vector<pii> range[MAX];

bool check(vector<pii> e) {
    vector<int> g[N];

    for(auto [A,B] : e) 
        g[A].pb(B), g[B].pb(A);

    queue<int> fila;
    vector<bool> vis(N);
    fila.push(0);
    vis[0] = 1;

    while(!fila.empty()) {
        int at = fila.front();
        fila.pop();

        for(int viz : g[at])
            if(!vis[viz]) fila.push(viz), vis[viz] = 1;
    }

    for(int i = 0; i < N; i++) if(!vis[i]) return 0;
    return 1;
}

void construct(vector<pii> edges){
    vector<int> U, V, A, B;
    map<pii,vector<pii>> point;

    // vamos anotar pontos e quantas ruas eles olham

    for(auto [i1, i2] : edges){
        int x1 = X[i1], y1 = Y[i1], x2 = X[i2], y2 = Y[i2];
        if(x1 == x2) {
            point[{x1+1, (y1+y2)/2}].pb({i1,i2});
            point[{x1-1, (y1+y2)/2}].pb({i1,i2});
        }
        if(y1 == y2) {
            point[{(x1+x2)/2, y1+1}].pb({i1,i2});
            point[{(x1+x2)/2, y1-1}].pb({i1,i2});
        }
    }

    queue<pii> fila;

    for(auto [p, qtd] : point)
        if(sz(qtd) == 1) fila.push(p);

    while(!point.empty()) {
        if(fila.empty()) fila.push((*point.begin()).fr);

        auto [a,b] = fila.front();
        fila.pop();

        if(point.count({a,b}) == 0) continue;
        auto [u,v] = point[{a,b}].back();
        point[{a,b}].pop_back();

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

        pii p = {a,b};
        if(X[u] == X[v]) p.fr = 2*X[u] - p.fr;
        else p.sc = 2*Y[u] - p.sc;

        for(int ind = 0; ind < sz(point[p]); ind++) {
            if(point[p][ind] == mk(u,v)) {
                point[p].erase(point[p].begin() + ind);
                break;
            }
        }

        if(point[p].empty()) point.erase(p);
        point.erase({a,b});
    }

    build(U, V, A, B);
}

int construct_roads(vector<int> x, vector<int> y) {
    N = sz(x);
    map<pii,int> ind;
    X = x;
    Y = y;

    for(int i = 0; i < N; i++)
        ind[{x[i], y[i]}] = i, v[x[i]].pb(y[i]);

    vector<pii> edges;

    for(int i = 2; i < MAX; i += 2) {
        sort(all(v[i]));
        for(int k = 0, last = -1; k < sz(v[i]); k++) {
            int j = v[i][k];
            // olhando o ponto (i,j)

            if(last == -1) last = j;
            if(k+1 == sz(v[i]) or v[i][k+1] - j != 2) range[i].pb({last, j}), last = -1;
            else edges.pb({ind[{i, j}], ind[{i, j+2}]});
        }
    }

    for(int i = 2; i < MAX; i += 2) {
        for(int j = 0, k = 0; j < sz(range[i]) and k < sz(range[i-2]); ) {
            if(range[i][j].sc < range[i-2][k].fr) j++;
            else if(range[i-2][k].sc < range[i][j].fr) k++;
            else {
                int p = min(range[i][j].sc, range[i-2][k].sc);
                edges.pb({ind[{i-2,p}], ind[{i,p}]});
                if(range[i][j].sc < range[i-2][k].sc) j++;
                else k++;
            }
        }
    }

    if(!check(edges)) return 0;

    construct(edges);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 211 ms 46616 KB Output is correct
10 Correct 15 ms 13404 KB Output is correct
11 Correct 95 ms 29692 KB Output is correct
12 Correct 24 ms 15328 KB Output is correct
13 Correct 23 ms 16852 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 219 ms 46644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 211 ms 46616 KB Output is correct
10 Correct 15 ms 13404 KB Output is correct
11 Correct 95 ms 29692 KB Output is correct
12 Correct 24 ms 15328 KB Output is correct
13 Correct 23 ms 16852 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 219 ms 46644 KB Output is correct
17 Correct 2 ms 9816 KB Output is correct
18 Correct 2 ms 9656 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 378 ms 75548 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 3 ms 10076 KB Output is correct
26 Correct 4 ms 10328 KB Output is correct
27 Correct 4 ms 10332 KB Output is correct
28 Correct 140 ms 35452 KB Output is correct
29 Correct 219 ms 48460 KB Output is correct
30 Correct 311 ms 62728 KB Output is correct
31 Correct 399 ms 75480 KB Output is correct
32 Correct 2 ms 9820 KB Output is correct
33 Correct 2 ms 9820 KB Output is correct
34 Correct 2 ms 9820 KB Output is correct
35 Correct 2 ms 9820 KB Output is correct
36 Correct 2 ms 9820 KB Output is correct
37 Correct 2 ms 9820 KB Output is correct
38 Correct 2 ms 9820 KB Output is correct
39 Correct 2 ms 9648 KB Output is correct
40 Correct 3 ms 9816 KB Output is correct
41 Correct 2 ms 9820 KB Output is correct
42 Correct 2 ms 9820 KB Output is correct
43 Correct 3 ms 10076 KB Output is correct
44 Correct 4 ms 10076 KB Output is correct
45 Correct 177 ms 40940 KB Output is correct
46 Correct 284 ms 55500 KB Output is correct
47 Correct 284 ms 55240 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 211 ms 46616 KB Output is correct
10 Correct 15 ms 13404 KB Output is correct
11 Correct 95 ms 29692 KB Output is correct
12 Correct 24 ms 15328 KB Output is correct
13 Correct 23 ms 16852 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 219 ms 46644 KB Output is correct
17 Correct 2 ms 9816 KB Output is correct
18 Correct 2 ms 9656 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 378 ms 75548 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 3 ms 10076 KB Output is correct
26 Correct 4 ms 10328 KB Output is correct
27 Correct 4 ms 10332 KB Output is correct
28 Correct 140 ms 35452 KB Output is correct
29 Correct 219 ms 48460 KB Output is correct
30 Correct 311 ms 62728 KB Output is correct
31 Correct 399 ms 75480 KB Output is correct
32 Correct 2 ms 9820 KB Output is correct
33 Correct 2 ms 9820 KB Output is correct
34 Correct 2 ms 9820 KB Output is correct
35 Correct 2 ms 9820 KB Output is correct
36 Correct 2 ms 9820 KB Output is correct
37 Correct 2 ms 9820 KB Output is correct
38 Correct 2 ms 9820 KB Output is correct
39 Correct 2 ms 9648 KB Output is correct
40 Correct 3 ms 9816 KB Output is correct
41 Correct 2 ms 9820 KB Output is correct
42 Correct 2 ms 9820 KB Output is correct
43 Correct 3 ms 10076 KB Output is correct
44 Correct 4 ms 10076 KB Output is correct
45 Correct 177 ms 40940 KB Output is correct
46 Correct 284 ms 55500 KB Output is correct
47 Correct 284 ms 55240 KB Output is correct
48 Correct 2 ms 9820 KB Output is correct
49 Correct 2 ms 9820 KB Output is correct
50 Correct 2 ms 9820 KB Output is correct
51 Correct 2 ms 9824 KB Output is correct
52 Correct 3 ms 10072 KB Output is correct
53 Correct 2 ms 9820 KB Output is correct
54 Correct 2 ms 9820 KB Output is correct
55 Correct 404 ms 72076 KB Output is correct
56 Incorrect 2 ms 9820 KB Given structure is not connected: There is no path between vertices 0 and 9
57 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 211 ms 46616 KB Output is correct
10 Correct 15 ms 13404 KB Output is correct
11 Correct 95 ms 29692 KB Output is correct
12 Correct 24 ms 15328 KB Output is correct
13 Correct 23 ms 16852 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 219 ms 46644 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Correct 346 ms 64924 KB Output is correct
21 Correct 340 ms 63840 KB Output is correct
22 Correct 349 ms 63840 KB Output is correct
23 Correct 334 ms 77852 KB Output is correct
24 Correct 115 ms 35928 KB Output is correct
25 Correct 169 ms 44992 KB Output is correct
26 Correct 163 ms 43456 KB Output is correct
27 Correct 356 ms 88488 KB Output is correct
28 Correct 379 ms 88484 KB Output is correct
29 Correct 381 ms 87652 KB Output is correct
30 Correct 409 ms 87648 KB Output is correct
31 Correct 2 ms 9816 KB Output is correct
32 Incorrect 25 ms 14216 KB Given structure is not connected: There is no path between vertices 0 and 1
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 211 ms 46616 KB Output is correct
10 Correct 15 ms 13404 KB Output is correct
11 Correct 95 ms 29692 KB Output is correct
12 Correct 24 ms 15328 KB Output is correct
13 Correct 23 ms 16852 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 219 ms 46644 KB Output is correct
17 Correct 392 ms 86880 KB Output is correct
18 Correct 403 ms 87140 KB Output is correct
19 Incorrect 329 ms 63840 KB Given structure is not connected: There is no path between vertices 0 and 19235
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 211 ms 46616 KB Output is correct
10 Correct 15 ms 13404 KB Output is correct
11 Correct 95 ms 29692 KB Output is correct
12 Correct 24 ms 15328 KB Output is correct
13 Correct 23 ms 16852 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 10076 KB Output is correct
16 Correct 219 ms 46644 KB Output is correct
17 Correct 2 ms 9816 KB Output is correct
18 Correct 2 ms 9656 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 378 ms 75548 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 3 ms 10076 KB Output is correct
26 Correct 4 ms 10328 KB Output is correct
27 Correct 4 ms 10332 KB Output is correct
28 Correct 140 ms 35452 KB Output is correct
29 Correct 219 ms 48460 KB Output is correct
30 Correct 311 ms 62728 KB Output is correct
31 Correct 399 ms 75480 KB Output is correct
32 Correct 2 ms 9820 KB Output is correct
33 Correct 2 ms 9820 KB Output is correct
34 Correct 2 ms 9820 KB Output is correct
35 Correct 2 ms 9820 KB Output is correct
36 Correct 2 ms 9820 KB Output is correct
37 Correct 2 ms 9820 KB Output is correct
38 Correct 2 ms 9820 KB Output is correct
39 Correct 2 ms 9648 KB Output is correct
40 Correct 3 ms 9816 KB Output is correct
41 Correct 2 ms 9820 KB Output is correct
42 Correct 2 ms 9820 KB Output is correct
43 Correct 3 ms 10076 KB Output is correct
44 Correct 4 ms 10076 KB Output is correct
45 Correct 177 ms 40940 KB Output is correct
46 Correct 284 ms 55500 KB Output is correct
47 Correct 284 ms 55240 KB Output is correct
48 Correct 2 ms 9820 KB Output is correct
49 Correct 2 ms 9820 KB Output is correct
50 Correct 2 ms 9820 KB Output is correct
51 Correct 2 ms 9824 KB Output is correct
52 Correct 3 ms 10072 KB Output is correct
53 Correct 2 ms 9820 KB Output is correct
54 Correct 2 ms 9820 KB Output is correct
55 Correct 404 ms 72076 KB Output is correct
56 Incorrect 2 ms 9820 KB Given structure is not connected: There is no path between vertices 0 and 9
57 Halted 0 ms 0 KB -