oj.uz

Submission #593990

# Submission time Handle Problem Language Result Execution time Memory
593990 2022-07-11T20:13:27 Z 1zaid1 Park (BOI16_park) C++17
100 / 100
 303 ms 62000 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 61548 KB Output is correct
2 Correct 247 ms 61632 KB Output is correct
3 Correct 272 ms 61580 KB Output is correct
4 Correct 253 ms 61544 KB Output is correct
5 Correct 259 ms 61572 KB Output is correct
6 Correct 255 ms 61796 KB Output is correct
7 Correct 253 ms 61516 KB Output is correct
8 Correct 229 ms 61512 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 8 ms 12072 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 14224 KB Output is correct
2 Correct 48 ms 14112 KB Output is correct
3 Correct 49 ms 14136 KB Output is correct
4 Correct 48 ms 14124 KB Output is correct
5 Correct 50 ms 14232 KB Output is correct
6 Correct 53 ms 14152 KB Output is correct
7 Correct 44 ms 13480 KB Output is correct
8 Correct 41 ms 13532 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 61548 KB Output is correct
2 Correct 247 ms 61632 KB Output is correct
3 Correct 272 ms 61580 KB Output is correct
4 Correct 253 ms 61544 KB Output is correct
5 Correct 259 ms 61572 KB Output is correct
6 Correct 255 ms 61796 KB Output is correct
7 Correct 253 ms 61516 KB Output is correct
8 Correct 229 ms 61512 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 8 ms 12072 KB Output is correct
11 Correct 51 ms 14224 KB Output is correct
12 Correct 48 ms 14112 KB Output is correct
13 Correct 49 ms 14136 KB Output is correct
14 Correct 48 ms 14124 KB Output is correct
15 Correct 50 ms 14232 KB Output is correct
16 Correct 53 ms 14152 KB Output is correct
17 Correct 44 ms 13480 KB Output is correct
18 Correct 41 ms 13532 KB Output is correct
19 Correct 303 ms 61824 KB Output is correct
20 Correct 300 ms 61784 KB Output is correct
21 Correct 294 ms 61820 KB Output is correct
22 Correct 280 ms 61728 KB Output is correct
23 Correct 288 ms 61708 KB Output is correct
24 Correct 298 ms 62000 KB Output is correct