oj.uz

Submission #837387

# Submission time Handle Problem Language Result Execution time Memory
837387 2023-08-25T10:09:15 Z QwertyPi Fountain Parks (IOI21_parks) C++17
5 / 100
 730 ms 129284 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

const int N_MAX = 2e5 + 11;

struct point{
    int x, y;
    bool operator< (const point& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
};

struct edge{
    int u, v;
};

int n;
map<point, int> mp;
vector<point> a;

struct DSU{
    int dsu[N_MAX];
    void init(int n){
        for(int i = 0; i < n; i++) dsu[i] = i;
    }
    int f(int x){ return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
    void g(int x, int y){ x = f(x), y = f(y); dsu[x] = y; }
} dsu;

vector<edge> construct_tree(){
    vector<edge> ans;
    dsu.init(n);
    for(int i = 0; i < n; i++){
        for(auto [dx, dy] : vector<pair<int, int>>{{0, -2}, {0, 2}, {2, 0}, {-2, 0}}){
            int nx = a[i].x + dx, ny = a[i].y + dy;
            if(mp.count({nx, ny})){
                int v = mp[{nx, ny}];
                if(dsu.f(i) != dsu.f(v)){
                    dsu.g(i, v);
                    ans.push_back({i, v});
                }
            }
        }
    }
    return ans;
}

vector<point> adj(int u, int v){
    assert(abs(a[u].x - a[v].x) + abs(a[u].y - a[v].y) == 2);
    if(a[u].x == a[v].x) return {{a[u].x - 1, (a[u].y + a[v].y) / 2}, {a[u].x + 1, (a[u].y + a[v].y) / 2}};
    else return {{(a[u].x + a[v].x) / 2, a[v].x - 1}, {(a[u].x + a[v].x) / 2, a[v].x + 1}};
}

vector<point> assign_benches(vector<edge> roads){
    vector<point> ans(roads.size());
    map<point, vector<int>> deg;
    for(int i = 0; i < (int) roads.size(); i++){
        int u = roads[i].u, v = roads[i].v;
        vector<point> p = adj(u, v);
        deg[p[0]].push_back(i);
        deg[p[1]].push_back(i);
    }
    vector<point> deg_0, deg_1;
    for(auto [p, v] : deg){
        if(v.size() == 0) deg_0.push_back(p);
        if(v.size() == 1) deg_1.push_back(p);
    }
    while(deg.size()){
        while(deg_0.size()) deg.erase(deg_0.back()), deg_0.pop_back();
        while(deg_1.size()){
            point v = deg_1.back(); deg_1.pop_back();
            if(deg[v].size() != 1) continue;

            int r = deg[v][0];
            ans[r] = v;

            int a = roads[r].u, b = roads[r].v;
            vector<point> p = adj(a, b);
            deg[p[0]].erase(find(all(deg[p[0]]), r));
            deg[p[1]].erase(find(all(deg[p[1]]), r));

            if(deg[p[0]].size() == 0) deg_0.push_back(p[0]);
            if(deg[p[0]].size() == 1) deg_1.push_back(p[0]);

            if(deg[p[1]].size() == 0) deg_0.push_back(p[1]);
            if(deg[p[1]].size() == 1) deg_1.push_back(p[1]);
        }

        if(deg.size()){
            auto [c, v] = *deg.begin(); deg.erase(deg.begin());
            if(v.empty()) continue;
            assert((int) v.size() == 2);
            int r = v[0];
            ans[r] = c;

            int a = roads[r].u, b = roads[r].v;
            vector<point> p = adj(a, b);
            deg[p[0]].erase(find(all(deg[p[0]]), r));
            deg[p[1]].erase(find(all(deg[p[1]]), r));

            if(deg[p[0]].size() == 0) deg_0.push_back(p[0]);
            if(deg[p[0]].size() == 1) deg_1.push_back(p[0]);

            if(deg[p[1]].size() == 0) deg_0.push_back(p[1]);
            if(deg[p[1]].size() == 1) deg_1.push_back(p[1]);
        }
    }
    return ans;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    for(int i = 0; i < n; i++){
        a.push_back({x[i], y[i]});
        mp[a[i]] = i;
    }

    vector<edge> edges = construct_tree();
    if((int) edges.size() < n - 1) return 0;
    vector<point> benches = assign_benches(edges);
    vector<int> u(n - 1), v(n - 1), a(n - 1), b(n - 1);
    for(int i = 0; i < n - 1; i++){
        u[i] = edges[i].u, v[i] = edges[i].v;
        a[i] = benches[i].x, b[i] = benches[i].y;
    }
    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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 399 ms 39028 KB Output is correct
10 Correct 25 ms 4184 KB Output is correct
11 Correct 173 ms 20952 KB Output is correct
12 Correct 37 ms 6028 KB Output is correct
13 Correct 36 ms 5320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 385 ms 39036 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 399 ms 39028 KB Output is correct
10 Correct 25 ms 4184 KB Output is correct
11 Correct 173 ms 20952 KB Output is correct
12 Correct 37 ms 6028 KB Output is correct
13 Correct 36 ms 5320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 385 ms 39036 KB Output is correct
17 Incorrect 1 ms 212 KB Tree (a[1], b[1]) = (3, 1) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=1 @(2, 4)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 399 ms 39028 KB Output is correct
10 Correct 25 ms 4184 KB Output is correct
11 Correct 173 ms 20952 KB Output is correct
12 Correct 37 ms 6028 KB Output is correct
13 Correct 36 ms 5320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 385 ms 39036 KB Output is correct
17 Incorrect 1 ms 212 KB Tree (a[1], b[1]) = (3, 1) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=1 @(2, 4)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 399 ms 39028 KB Output is correct
10 Correct 25 ms 4184 KB Output is correct
11 Correct 173 ms 20952 KB Output is correct
12 Correct 37 ms 6028 KB Output is correct
13 Correct 36 ms 5320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 385 ms 39036 KB Output is correct
17 Incorrect 1 ms 212 KB Tree (a[1], b[1]) = (199999, 199999) is not adjacent to edge between u[1]=0 @(200000, 2) and v[1]=2 @(199998, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 399 ms 39028 KB Output is correct
10 Correct 25 ms 4184 KB Output is correct
11 Correct 173 ms 20952 KB Output is correct
12 Correct 37 ms 6028 KB Output is correct
13 Correct 36 ms 5320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 385 ms 39036 KB Output is correct
17 Runtime error 730 ms 129284 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 399 ms 39028 KB Output is correct
10 Correct 25 ms 4184 KB Output is correct
11 Correct 173 ms 20952 KB Output is correct
12 Correct 37 ms 6028 KB Output is correct
13 Correct 36 ms 5320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 385 ms 39036 KB Output is correct
17 Incorrect 1 ms 212 KB Tree (a[1], b[1]) = (3, 1) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=1 @(2, 4)
18 Halted 0 ms 0 KB -