oj.uz

Submission #698360

# Submission time Handle Problem Language Result Execution time Memory
698360 2023-02-13T09:30:25 Z sysia Park (BOI16_park) C++17
100 / 100
 454 ms 73256 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
typedef long double ld;

struct circle{
    int x, y, r;
    circle(int _x = 0, int _y = 0, int _r = 0){ x = _x, y = _y, r = _r;}
    ld dist(circle &he){ return sqrtl(ld((he.x - x) * (he.x - x) + (he.y - y) * (he.y - y))) - (ld)he.r - (ld)r;}
    void read(){cin >> x >> y >> r;}
};

struct DSU{
    vector<int>rep, sz;

    DSU(int n){
        rep.resize(n);
        iota(rep.begin(), rep.end(), 0);
        sz.assign(n, 1);
    }

    int f(int a){return a == rep[a] ? a : rep[a] = f(rep[a]);}
    bool sameset(int a, int b){ return f(a) == f(b);}

    bool u(int a, int b){
        a = f(a); b = f(b);
        if (a == b) return 0;
        if (sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        rep[b] = a;
        return 1;
    }
};

void solve(){
    int n, m; cin >> n >> m;
    int w, h; cin >> w >> h;
    vector<circle>circ(n+1);
    for (int i = 1; i<=n; i++) circ[i].read();
    cerr << fixed << setprecision(3);
    vector<tuple<ld, int, int>>ord;
    for (int i = 1; i<=n; i++){
        for (int j = i+1; j<=n; j++){
            ord.emplace_back(circ[i].dist(circ[j]), i, j);
        }
        //sciany:
        ord.emplace_back((ld)(circ[i].x - circ[i].r), i, n+1); //lewa 
        ord.emplace_back((ld)(circ[i].y - circ[i].r), i, n+2); //dolna
        ord.emplace_back((ld)(w - circ[i].x - circ[i].r), i, n+3); //prawa
        ord.emplace_back((ld)(h - circ[i].y - circ[i].r), i, n+4); //gorna
    }    
    for (auto [d, i, j]: ord){
        debug(d, i, j);
    }
    DSU dsu(n+5);
    sort(ord.begin(), ord.end());
    
    vector<tuple<int, int, int>>que;
    for (int i = 1; i<=m; i++){
        int r, e; cin >> r >> e;
        e += n;
        que.emplace_back(r, e, i);
    }
    sort(que.begin(), que.end());
    int ptr = 0;
    vector<string>ans(m+1);
    auto check = [&](int a, int b){
        if (a == b) return 1;
        if (a > b) swap(a, b);
        //a < b, c < d
        int c = -1, d = -1;
        for (int j = n+1; j<=n+4; j++) {
            if (j == a || j == b) continue;
            if (c == -1) c = j;
            else d = j;
        }
        debug(a, b, c, d);
        if (b - a == 2){
            //naprzemianlegle
            if (dsu.sameset(c, d) || dsu.sameset(a, b) ||
                (a == n+1 && (dsu.sameset(a, c) || dsu.sameset(b, d))) || 
                (a == n+2 && (dsu.sameset(a, d) || dsu.sameset(b, c)))) return 0;
        } else {
            //sasiadujace
            int between = (b == n+4 ? (a == n + 1 ? a : b) : b);
            debug(between);
            for (int j = n+1; j<=n+4; j++){
                if (j != between && dsu.sameset(between, j)) {
                    return 0;
                }
            }
        }
        return 1;
    };
    for (int i = 0; i<m; i++){
        auto [r, e, idx] = que[i];
        while (ptr < (int)ord.size() && (ld)2 * r > get<0>(ord[ptr])){
            auto [d, a, b] = ord[ptr];
            debug(a, b);
            dsu.u(a, b);
            ptr++;
        }
        debug(r, e);
        for (int j = n+1; j<=n+4; j++){
            if (check(e, j)) {
                ans[idx] += (char)(j-n + '0');
            }
        }
    }
    for (int i = 1; i<=m; i++) cout << ans[i] << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();
}

Compilation message

park.cpp: In function 'void solve()':
park.cpp:77:15: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   77 |     for (auto [d, i, j]: ord){
      |               ^~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 66184 KB Output is correct
2 Correct 409 ms 66084 KB Output is correct
3 Correct 405 ms 66176 KB Output is correct
4 Correct 402 ms 66200 KB Output is correct
5 Correct 405 ms 66124 KB Output is correct
6 Correct 418 ms 66176 KB Output is correct
7 Correct 386 ms 66184 KB Output is correct
8 Correct 375 ms 66124 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 216 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7560 KB Output is correct
2 Correct 41 ms 7564 KB Output is correct
3 Correct 43 ms 8512 KB Output is correct
4 Correct 41 ms 8596 KB Output is correct
5 Correct 42 ms 8636 KB Output is correct
6 Correct 42 ms 8656 KB Output is correct
7 Correct 42 ms 7356 KB Output is correct
8 Correct 38 ms 7360 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 66184 KB Output is correct
2 Correct 409 ms 66084 KB Output is correct
3 Correct 405 ms 66176 KB Output is correct
4 Correct 402 ms 66200 KB Output is correct
5 Correct 405 ms 66124 KB Output is correct
6 Correct 418 ms 66176 KB Output is correct
7 Correct 386 ms 66184 KB Output is correct
8 Correct 375 ms 66124 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 43 ms 7560 KB Output is correct
12 Correct 41 ms 7564 KB Output is correct
13 Correct 43 ms 8512 KB Output is correct
14 Correct 41 ms 8596 KB Output is correct
15 Correct 42 ms 8636 KB Output is correct
16 Correct 42 ms 8656 KB Output is correct
17 Correct 42 ms 7356 KB Output is correct
18 Correct 38 ms 7360 KB Output is correct
19 Correct 441 ms 73180 KB Output is correct
20 Correct 443 ms 73256 KB Output is correct
21 Correct 454 ms 73180 KB Output is correct
22 Correct 439 ms 73052 KB Output is correct
23 Correct 441 ms 73128 KB Output is correct
24 Correct 432 ms 73196 KB Output is correct