oj.uz

Submission #599984

# Submission time Handle Problem Language Result Execution time Memory
599984 2022-07-20T11:09:54 Z Valaki2 Fountain Parks (IOI21_parks) C++17
5 / 100
 500 ms 57540 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

#define x X
#define y Y

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 2e5;
const vector<pii > directions = {mp(-2, 0), mp(0, -2), mp(0, 2), mp(2, 0)};

bool check_possibility(int n, vector<int> x, vector<int> y) {
    unordered_map<int, unordered_map<int, bool> > m;
    unordered_map<int, unordered_map<int, int> > f;
    for(int i = 0; i < n; i++) {
        f[x[i]][y[i]] = i + 1;
    }
    queue<int> q;
    q.push(0);
    m[x[0]][y[0]] = true;
    int cnt = 0;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        cnt++;
        for(pii dir : directions) {
            pii new_point = mp(x[cur] + dir.fi, y[cur] + dir.se);
            if(f[new_point.fi][new_point.se] && !m[new_point.fi][new_point.se]) {
                m[new_point.fi][new_point.se] = true;
                int new_id = f[new_point.fi][new_point.se] - 1;
                q.push(new_id);
            }
        }
    }
    return (cnt == n);
}

struct fountain {
    int x, y, id;
    fountain() : x(0), y(0), id(-1) {}
    fountain(int x_, int y_, int id_) :
        x(x_), y(y_), id(id_) {}
};

int n;
vector<fountain > points;
vector<int> x;
vector<int> y;
unordered_map<int, unordered_map<int, int> > fountain_at;

unordered_map<int, unordered_map<int, bool> > bench_at;
vector<int> ans_u;
vector<int> ans_v;
vector<int> ans_a;
vector<int> ans_b;

void build_road_bench(int road_u, int road_v, pii bench_pos) {
    ans_u.pb(road_u);
    ans_v.pb(road_v);
    ans_a.pb(bench_pos.fi);
    ans_b.pb(bench_pos.se);
    bench_at[bench_pos.fi][bench_pos.se] = true;
}

vector<fountain> by_a;
vector<fountain> by_b;
vector<fountain> by_c;

bool sort_by_y(const fountain &a, const fountain &b) {
    return a.y < b.y;
}

void solve() {
    /*for(fountain p : points) {
        if(p.x == 2) {
            by_a.pb(p);
        }
        if(p.x == 4) {
            by_b.pb(p);
        }
        if(p.x == 6) {
            by_c.pb(p);
        }
    }
    sort(by_a.begin(), by_a.end(), sort_by_y);
    sort(by_b.begin(), by_b.end(), sort_by_y);
    sort(by_c.begin(), by_c.end(), sort_by_y);*/
    // type A and E
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[2][i], b = fountain_at[2][i + 2];
        if(a && b) {
            build_road_bench(a - 1, b - 1, mp(1, i + 1));
        }
        a = fountain_at[6][i], b = fountain_at[6][i + 2];
        if(a && b) {
            build_road_bench(a - 1, b - 1, mp(7, i + 1));
        }
    }
    // type B
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[2][i], b = fountain_at[2][i + 2],
            c = fountain_at[4][i], d = fountain_at[4][i + 2];
        if((b && d) && (!a || !c)) {
            build_road_bench(b - 1, d - 1, mp(3, i + 1));
        }
    }
    // type C
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[4][i], b = fountain_at[4][i + 2];
        if(a && b) {
            if(!bench_at[3][i + 1]) {
                build_road_bench(a - 1, b - 1, mp(3, i + 1));
            } else {
                build_road_bench(a - 1, b - 1, mp(5, i + 1));
            }
        }
    }
    // type D
    for(int i = 2; i <= maxn; i += 2) {
        int a = fountain_at[4][i], b = fountain_at[4][i + 2],
            c = fountain_at[6][i], d = fountain_at[6][i + 2];
        if((b && d) && (!a || !c)) {
            if(!bench_at[5][i + 1]) {
                build_road_bench(b - 1, d - 1, mp(5, i + 1));
            } else {
                build_road_bench(b - 1, d - 1, mp(5, i + 3));
            }
        }
    }
}

#undef x
#undef y
int construct_roads(vector<int> x, vector<int> y) {
    // edge case
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    // sample solution
    /*vector<int> u, v, a, b;
    u.push_back(0);
    v.push_back(1);
    a.push_back(x[0]+1);
    b.push_back(y[0]-1);
    build(u, v, a, b);*/
    n = x.size();
    if(!check_possibility(n, x, y)) {
        return 0;
    }
    X = x;
    Y = y;
    points.assign(n, fountain());
    for(int i = 0; i < n; i++) {
        points[i] = fountain(x[i], y[i], i);
        fountain_at[x[i]][y[i]] = i + 1;
    }
    solve();
    // build solution
    build(ans_u, ans_v, ans_a, ans_b);
    return 1;
}

/*
5
4 4
4 6
6 4
4 2
2 4
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 36 ms 13908 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 43 ms 13936 KB Output is correct
5 Correct 36 ms 13948 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 178 ms 28760 KB Output is correct
10 Correct 53 ms 15236 KB Output is correct
11 Correct 88 ms 21760 KB Output is correct
12 Correct 55 ms 16000 KB Output is correct
13 Correct 21 ms 7500 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 185 ms 28780 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 36 ms 13908 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 43 ms 13936 KB Output is correct
5 Correct 36 ms 13948 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 178 ms 28760 KB Output is correct
10 Correct 53 ms 15236 KB Output is correct
11 Correct 88 ms 21760 KB Output is correct
12 Correct 55 ms 16000 KB Output is correct
13 Correct 21 ms 7500 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 185 ms 28780 KB Output is correct
17 Incorrect 38 ms 13960 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 36 ms 13908 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 43 ms 13936 KB Output is correct
5 Correct 36 ms 13948 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 178 ms 28760 KB Output is correct
10 Correct 53 ms 15236 KB Output is correct
11 Correct 88 ms 21760 KB Output is correct
12 Correct 55 ms 16000 KB Output is correct
13 Correct 21 ms 7500 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 185 ms 28780 KB Output is correct
17 Incorrect 38 ms 13960 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 36 ms 13908 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 43 ms 13936 KB Output is correct
5 Correct 36 ms 13948 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 178 ms 28760 KB Output is correct
10 Correct 53 ms 15236 KB Output is correct
11 Correct 88 ms 21760 KB Output is correct
12 Correct 55 ms 16000 KB Output is correct
13 Correct 21 ms 7500 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 185 ms 28780 KB Output is correct
17 Incorrect 38 ms 13876 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 36 ms 13908 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 43 ms 13936 KB Output is correct
5 Correct 36 ms 13948 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 178 ms 28760 KB Output is correct
10 Correct 53 ms 15236 KB Output is correct
11 Correct 88 ms 21760 KB Output is correct
12 Correct 55 ms 16000 KB Output is correct
13 Correct 21 ms 7500 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 185 ms 28780 KB Output is correct
17 Incorrect 500 ms 57540 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 36 ms 13908 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 43 ms 13936 KB Output is correct
5 Correct 36 ms 13948 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 178 ms 28760 KB Output is correct
10 Correct 53 ms 15236 KB Output is correct
11 Correct 88 ms 21760 KB Output is correct
12 Correct 55 ms 16000 KB Output is correct
13 Correct 21 ms 7500 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 436 KB Output is correct
16 Correct 185 ms 28780 KB Output is correct
17 Incorrect 38 ms 13960 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -