oj.uz

Submission #1061704

# Submission time Handle Problem Language Result Execution time Memory
1061704 2024-08-16T12:01:36 Z mc061 Fountain Parks (IOI21_parks) C++17
5 / 100
 505 ms 56768 KB 
#include <bits/stdc++.h>
using namespace std;

map<pair<int, int>, int> vid;
int di[2] = {2, 0};
int dj[2] = {0, 2};

struct edge {
    int i1, j1, i2, j2;
};

vector<edge> edges;
const int N = 2e5+6;
struct DSU {
    int p[N]={};
    int sz[N];
    DSU() {
        iota(p, p+N, 0);
        fill(sz, sz+N, 1);
    }
    int get(int a) {
        return p[a] = (a == p[a] ? a : get(p[a]));
    }
    void merge(int a, int b) {
        int x = get(a), y = get(b);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
    }
};

vector<edge> horizontal, vertical;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
bool try_build() {
    //0 - up(hor)   (from road: -1;+1)
    //1 - down(hor) (from road: +1;+1)
    //2 - left(ver) (from road: +1;-1)
    //3 - right(ver)(from road: +1;+1)

    vector<int> tlx = {-1, 1, 1, 1};
    vector<int> tly = {1, 1, -1, 1};

    vector<int> dx = {0, 0, 2, 2};
    vector<int> dy = {2, 2, 0, 0};

    map<pair<int, int>, int> bench_dir;
    for (const auto& e : horizontal) {
        bench_dir[{e.i1-1, e.j1+1}] = 0;
    }
    
    auto sieve_down = [&] (int bi, int bj) -> void {
        bench_dir.erase({bi, bj});
        bi += 2;
        while (bench_dir.count({bi, bj})) {
            bench_dir[{bi, bj}] = 1;
            bi += 2;
        }
        bench_dir[{bi, bj}] = 1;
    };

    for (const auto& e : vertical) {
        int wi_left = e.i1+1;
        int wj_left = e.j1-1;

        int wi_right = e.i1+1;
        int wj_right = e.j1+1;

        if (bench_dir.count({wi_left, wj_left})) {
            if (!bench_dir.count({wi_right, wj_right})) {
                bench_dir[{wi_right, wj_right}] = 3;
                continue;
            }
            int prev_dir = bench_dir[{wi_left, wj_left}];
            
            if (prev_dir == 0) {
                sieve_down(wi_left, wj_left);
                bench_dir[{wi_left, wj_left}] = 2;
                continue;
            }
            if (prev_dir == 1) {
                int prev_dir2 = bench_dir[{wi_right, wj_right}];
                if (prev_dir2 == 1) {
                    return false;
                }
            }
            sieve_down(wi_right, wj_right);
            bench_dir[{wi_right, wj_right}] = 3;
        }
    }
    map<array<int, 4>, pair<int, int>> road_to_bench;
    for (const auto& [x, y] : bench_dir) {         
        int tx = x.first-tlx[y];
        int ty = x.second-tly[y];
        int bx = tx+dx[y];
        int by = ty+dy[y];
        road_to_bench[{tx, ty, bx, by}] = {x.first, x.second};
    }

    vector<int> u, v, a, b;

    for (const auto& e : horizontal) {
        u.push_back(vid[{e.i1, e.j1}]);
        v.push_back(vid[{e.i2, e.j2}]);
        a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first);
        b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second);
    }
    for (const auto& e : vertical) {
        u.push_back(vid[{e.i1, e.j1}]);
        v.push_back(vid[{e.i2, e.j2}]);
        a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first);
        b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second);
    }
    build(u, v, a, b);
    return true;
}

int construct_roads(vector<int> x, vector<int> y) {
    const int n = x.size();
    for (int i = 0; i < n; ++i) {
        vid[{x[i], y[i]}] = i;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            int ni = x[i] + di[j];
            int nj = y[i] + dj[j];
            auto it = vid.find({ni, nj});
            if (it == vid.end()) continue;
            edges.push_back({x[i], y[i], ni, nj});
        }
    }

    DSU d;
    for (const edge& e : edges) {
        bool hor = e.i1 == e.i2;
        int id1 = vid[{e.i1, e.j1}];
        int id2 = vid[{e.i2, e.j2}];
        if (d.get(id1) == d.get(id2)) continue;
        d.merge(id1, id2);
        if (!hor) vertical.push_back(e);
        else horizontal.push_back(e);
    }

    if (d.sz[d.get(0)] != n) return 0;

    sort(vertical.begin(), vertical.end(), [&](const edge& a, const edge& b) {
        if (a.i1 != b.i1) return a.i1 < b.i1;
        return a.j1 < b.j1; 
    });
    for (int i = 0; i < 5; ++i) {
        int j = try_build();
        if (j == 1) return true;
    }
    return false;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 252 ms 32448 KB Output is correct
10 Correct 13 ms 4956 KB Output is correct
11 Correct 82 ms 18352 KB Output is correct
12 Correct 21 ms 6488 KB Output is correct
13 Correct 28 ms 7888 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 3 ms 2140 KB Output is correct
16 Correct 255 ms 32460 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 252 ms 32448 KB Output is correct
10 Correct 13 ms 4956 KB Output is correct
11 Correct 82 ms 18352 KB Output is correct
12 Correct 21 ms 6488 KB Output is correct
13 Correct 28 ms 7888 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 3 ms 2140 KB Output is correct
16 Correct 255 ms 32460 KB Output is correct
17 Incorrect 1 ms 2136 KB a[1] = 0 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 252 ms 32448 KB Output is correct
10 Correct 13 ms 4956 KB Output is correct
11 Correct 82 ms 18352 KB Output is correct
12 Correct 21 ms 6488 KB Output is correct
13 Correct 28 ms 7888 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 3 ms 2140 KB Output is correct
16 Correct 255 ms 32460 KB Output is correct
17 Incorrect 1 ms 2136 KB a[1] = 0 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 252 ms 32448 KB Output is correct
10 Correct 13 ms 4956 KB Output is correct
11 Correct 82 ms 18352 KB Output is correct
12 Correct 21 ms 6488 KB Output is correct
13 Correct 28 ms 7888 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 3 ms 2140 KB Output is correct
16 Correct 255 ms 32460 KB Output is correct
17 Incorrect 1 ms 1884 KB a[1] = 0 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 252 ms 32448 KB Output is correct
10 Correct 13 ms 4956 KB Output is correct
11 Correct 82 ms 18352 KB Output is correct
12 Correct 21 ms 6488 KB Output is correct
13 Correct 28 ms 7888 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 3 ms 2140 KB Output is correct
16 Correct 255 ms 32460 KB Output is correct
17 Incorrect 505 ms 56768 KB a[100000] = 0 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 252 ms 32448 KB Output is correct
10 Correct 13 ms 4956 KB Output is correct
11 Correct 82 ms 18352 KB Output is correct
12 Correct 21 ms 6488 KB Output is correct
13 Correct 28 ms 7888 KB Output is correct
14 Correct 2 ms 1884 KB Output is correct
15 Correct 3 ms 2140 KB Output is correct
16 Correct 255 ms 32460 KB Output is correct
17 Incorrect 1 ms 2136 KB a[1] = 0 is not an odd integer
18 Halted 0 ms 0 KB -