Submission #593990

#	Time	Username	Problem	Language	Result	Execution time	Memory
593990		1zaid1	Park (BOI16_park)	C++17	100 / 100	303 ms	62000 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define int long long
const int M = 5e5+5;
struct tre{int x, y, r;};
struct edg{int a, b, c;};
 
vector<pair<int, int>> node[M];
int p[M], rnk[M];
 
int find(int s) {
    return (s-p[s]?p[s]=find(p[s]):s);
}
 
void uni(int a, int b) {
    if (rnk[a] < rnk[b]) swap(a, b);
    if (rnk[a] == rnk[b]) rnk[a]++;
    p[b] = a;
}
 
int nxt[M][30], mx[M][30], d[M];
void dfs(int s, int parent = 1) {
    nxt[s][0] = parent;
    for (int i = 1; i < 20; i++) {
        mx[s][i] = max(mx[s][i-1], mx[nxt[s][i-1]][i-1]);
        nxt[s][i] = nxt[nxt[s][i-1]][i-1];
    }
 
    for (auto [i, x]:node[s]) {
        if (i != parent) {
            mx[i][0] = x;
            d[i] = d[s]+1;
            dfs(i, s);
        }
    }
}
 
int lca(int a, int b) {
    if (d[a] < d[b]) swap(a, b);
    int x = a, y = b;
    int l = 0;
    while (d[a]-d[b] > 0) {
        if ((d[a]-d[b])&(1<<l)) a = nxt[a][l];
        l++;
    }
 
    l = 20;
    while (a != b) {
        while (l >= 0 && nxt[a][l] == nxt[b][l]) l--;
        if (l < 0) {
            a = nxt[a][0];
            break;
        }
 
        a = nxt[a][l];
        b = nxt[b][l];
    }
 
    int m = 0;
    for (int i = 0; i < 20; i++) {
        if ((d[x]-d[a])&(1<<i)) {
            m = max(m, mx[x][i]);
            x = nxt[x][i];
        }
 
        if ((d[y]-d[a])&(1<<i)) {
            m = max(m, mx[y][i]);
            y = nxt[y][i];
        }
    }
 
    return m;
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    vector<tre> tree;
 
    int n, q, w, h;
    cin >> n >> q;
    cin >> w >> h;
    for (int i = 1; i <= n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        tree.push_back({x, y, r});
    }
 
    vector<edg> e;
    int A = n+1, B = n+2, C = n+3, D = n+4;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int dx = tree[i].x-tree[j].x;
            int dy = tree[i].y-tree[j].y;
            int d = floor(sqrt(dx*dx+dy*dy)) - tree[i].r - tree[j].r;
            e.push_back({i+1, j+1, d});
        }
 
        e.push_back({A, i+1, (tree[i].x-tree[i].r)});
        e.push_back({D, i+1, (tree[i].y-tree[i].r)});
        e.push_back({C, i+1, (w-tree[i].x-tree[i].r)});
        e.push_back({B, i+1, (h-tree[i].y-tree[i].r)});
    }
 
    for (int i = 1; i <= n+4; i++) p[i] = i;
 
    sort(e.begin(), e.end(), [](edg a, edg b) {return a.c < b.c;});
    for (int i = 0; i < e.size(); i++) {
        auto [a, b, c] = e[i];
        if (find(a) != find(b)) {
            uni(find(a), find(b));
            node[a].push_back({b, c});
            node[b].push_back({a, c});
        }
    }
 
    // for (int i = 1; i <= n+4; i++) {
    //     for (auto [j, x]:node[i]) cout << "tst" << i << " " << j << " " << x << endl;
    // }
    dfs(1);
    int AB = lca(A, B);
    int AC = lca(A, C);
    int AD = lca(A, D);
    int BC = lca(B, C);
    int BD = lca(B, D);
    int CD = lca(C, D);
 
    // cout << "AB: " << AB << endl;
    // cout << "AC: " << AC << endl;
    // cout << "AD: " << AD << endl;
    // cout << "BC: " << BC << endl;
    // cout << "BD: " << BD << endl;
    // cout << "CD: " << CD << endl;
    while (q--) {
        int p, r;
        cin >> r >> p;
 
        set<int> ans = {p};
        if (p == 1 || p == 2) {
            if (BD >= 2*r && AD >= 2*r && CD >= 2*r) {
                ans.insert(1);
                ans.insert(2);
            }
        }
 
        if (p == 4 || p == 3) {
            if (BD >= 2*r && AB >= 2*r && BC >= 2*r) {
                ans.insert(4);
                ans.insert(3);
            }
        }
// ---------------------LR-------------------------------
        if (p == 1 || p == 4) {
            if (AC >= 2*r && AB >= 2*r && AD >= 2*r) {
                ans.insert(1);
                ans.insert(4);
            }
        }
 
        if (p == 2 || p == 3) {
            if (AC >= 2*r && BC >= 2*r && CD >= 2*r) {
                ans.insert(2);
                ans.insert(3);
            }
        }
// --------------------UD-----------------------------------
        if (p == 1 || p == 3) {
            if (AC >= 2*r && BD >= 2*r && BC >= 2*r && AD >= 2*r) {
                ans.insert(1);
                ans.insert(3);
            }
        }
 
        if (p == 2 || p == 4) {
            if (AC >= 2*r && BD >= 2*r && AB >= 2*r && CD >= 2*r) {
                ans.insert(2);
                ans.insert(4);
            }
        }
// --------------------CR-----------------------------------
        for (int i:ans) cout << i; cout << endl;
    }
    
    return 0;
}
 
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
 
1 B 2
1 4 3
1 5 3
2 B 0
2 A 5
3 4 1
3 D 1
4 3 1
4 1 3
5 C 0
5 1 3
A 2 5
B 2 0
B 1 2
C 5 0
D 3 1
*/

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:109:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < e.size(); i++) {
      |                     ~~^~~~~~~~~~
park.cpp:182:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  182 |         for (int i:ans) cout << i; cout << endl;
      |         ^~~
park.cpp:182:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  182 |         for (int i:ans) cout << i; cout << endl;
      |                                    ^~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42