oj.uz

Submission #936529

# Submission time Handle Problem Language Result Execution time Memory
936529 2024-03-02T05:05:18 Z yellowtoad Park (BOI16_park) C++17
100 / 100
 553 ms 73088 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#define f first
#define s second
#define int long long
using namespace std;
 
int n, m, w, h, p[2010], cur, can[100010][5];
pair<pair<int,int>,int> b[100010];
pair<int,pair<int,int>> a[2010];
vector<pair<long double,pair<int,int>>> edge;
 
int dsu(int u) {
    if (u == p[u]) return u;
    return (p[u] = dsu(p[u]));
}
 
signed main() {
    cin >> n >> m >> w >> h;
    for (int i = 1; i <= n; i++) cin >> a[i].s.f >> a[i].s.s >> a[i].f;
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) edge.push_back({(long double)sqrt((a[i].s.f-a[j].s.f)*(a[i].s.f-a[j].s.f)+(a[i].s.s-a[j].s.s)*(a[i].s.s-a[j].s.s))-a[i].f-a[j].f,{i,j}});
        edge.push_back({a[i].s.s-a[i].f,{i,n+1}});
        edge.push_back({w-a[i].s.f-a[i].f,{i,n+2}});
        edge.push_back({h-a[i].s.s-a[i].f,{i,n+3}});
        edge.push_back({a[i].s.f-a[i].f,{i,n+4}});
    }
    sort(edge.begin(),edge.end());
    for (int i = 1; i <= n+4; i++) p[i] = i;
    for (int i = 1; i <= m; i++) {
        cin >> b[i].f.f >> b[i].f.s;
        b[i].s = i;
    }
    sort(b+1,b+m+1);
    for (int i = 1; i <= m; i++) {
        while ((cur < edge.size()) && (edge[cur].f < b[i].f.f*2)) {
            p[dsu(edge[cur].s.f)] = p[dsu(edge[cur].s.s)];
            cur++;
        }
        for (int j = 1; j <= 4; j++) can[b[i].s][j] = 1;
        if (p[dsu(n+1)] == p[dsu(n+2)]) {
            if (b[i].f.s == 2) can[b[i].s][1] = can[b[i].s][3] = can[b[i].s][4] = 0;
            else can[b[i].s][2] = 0;
        }
        if (p[dsu(n+1)] == p[dsu(n+3)]) {
            if ((b[i].f.s == 2) || (b[i].f.s == 3)) can[b[i].s][1] = can[b[i].s][4] = 0;
            else can[b[i].s][3] = can[b[i].s][2] = 0;
        }
        if (p[dsu(n+1)] == p[dsu(n+4)]) {
            if (b[i].f.s == 1) can[b[i].s][2] = can[b[i].s][3] = can[b[i].s][4] = 0;
            else can[b[i].s][1] = 0;
        }
        if (p[dsu(n+2)] == p[dsu(n+3)]) {
            if (b[i].f.s == 3) can[b[i].s][1] = can[b[i].s][2] = can[b[i].s][4] = 0;
            else can[b[i].s][3] = 0;
        }
        if (p[dsu(n+2)] == p[dsu(n+4)]) {
            if ((b[i].f.s == 1) || (b[i].f.s == 2)) can[b[i].s][3] = can[b[i].s][4] = 0;
            else can[b[i].s][1] = can[b[i].s][2] = 0;
        }
        if (p[dsu(n+3)] == p[dsu(n+4)]) {
            if (b[i].f.s == 4) can[b[i].s][1] = can[b[i].s][2] = can[b[i].s][3] = 0;
            else can[b[i].s][4] = 0;
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= 4; j++) if (can[i][j]) cout << j;
        cout << endl;
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:38:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while ((cur < edge.size()) && (edge[cur].f < b[i].f.f*2)) {
      |                 ~~~~^~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 68284 KB Output is correct
2 Correct 351 ms 69552 KB Output is correct
3 Correct 349 ms 69088 KB Output is correct
4 Correct 352 ms 70064 KB Output is correct
5 Correct 353 ms 69536 KB Output is correct
6 Correct 359 ms 68948 KB Output is correct
7 Correct 331 ms 69044 KB Output is correct
8 Correct 331 ms 69292 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4544 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 7796 KB Output is correct
2 Correct 171 ms 9156 KB Output is correct
3 Correct 163 ms 8748 KB Output is correct
4 Correct 163 ms 8656 KB Output is correct
5 Correct 169 ms 9412 KB Output is correct
6 Correct 165 ms 8900 KB Output is correct
7 Correct 163 ms 8016 KB Output is correct
8 Correct 162 ms 8136 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 68284 KB Output is correct
2 Correct 351 ms 69552 KB Output is correct
3 Correct 349 ms 69088 KB Output is correct
4 Correct 352 ms 70064 KB Output is correct
5 Correct 353 ms 69536 KB Output is correct
6 Correct 359 ms 68948 KB Output is correct
7 Correct 331 ms 69044 KB Output is correct
8 Correct 331 ms 69292 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4544 KB Output is correct
11 Correct 163 ms 7796 KB Output is correct
12 Correct 171 ms 9156 KB Output is correct
13 Correct 163 ms 8748 KB Output is correct
14 Correct 163 ms 8656 KB Output is correct
15 Correct 169 ms 9412 KB Output is correct
16 Correct 165 ms 8900 KB Output is correct
17 Correct 163 ms 8016 KB Output is correct
18 Correct 162 ms 8136 KB Output is correct
19 Correct 510 ms 71712 KB Output is correct
20 Correct 517 ms 72628 KB Output is correct
21 Correct 513 ms 73088 KB Output is correct
22 Correct 508 ms 71832 KB Output is correct
23 Correct 512 ms 72472 KB Output is correct
24 Correct 553 ms 71280 KB Output is correct