oj.uz

Submission #862872

# Submission time Handle Problem Language Result Execution time Memory
862872 2023-10-19T07:38:09 Z Ellinor Park (BOI16_park) C++14
100 / 100
 279 ms 58956 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define rrep(i, a, b) for (int i = (a) - 1; i >= int(b); i--)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back
#define all(x) x.begin(), x.end()

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

#define int ll
#define float double

//

int n, m;
int w, h;
int x, y, r;
int e; // r, e

vector<array<int, 3>> trees;
vector<array<int, 3>> visitors;

int nn;
//   3
// 0   2
//   1

vector<array<int, 3>> edges; // w, n, n

vector<int> pars, _size;

vector<string> ans;

int find_par(int node) {
    if (pars[node] == node) return node;
    return pars[node] = find_par(pars[node]);
}

void union_sets(int a, int b) {
    a = find_par(a);
    b = find_par(b);
    if (a != b) {
        if (_size[a] < _size[b]) swap(a, b);
        pars[b] = a;
        _size[a] += _size[b];
    }
}

//

int32_t main()
{
    fast();
    cin >> n >> m;
    nn = n + 4;
    cin >> w >> h;
    rep(i,0,n) {
        cin >> x >> y >> r;
        //
        edges.pb({x - r, 0, i + 4});
        edges.pb({y - r, 1, i + 4});
        edges.pb({w - x - r, 2, i + 4});
        edges.pb({h - y - r, 3, i + 4});
        //
        rep(j,0,trees.size()) {
            double di = sqrt(abs(trees[j][0] - x) * abs(trees[j][0] - x) + abs(trees[j][1] - y) * abs(trees[j][1] - y)); // !
            int dii = int(di); // ?
            dii -= r;
            dii -= trees[j][2];
            edges.pb({dii, j + 4, i + 4});
        }
        trees.pb({x, y, r});
    }
    rep(i,0,m) {
        cin >> r >> e;
        r *= 2;
        visitors.pb({r, e, i});
    }
    sort(all(visitors));
    sort(all(edges));

    // cerr << edges.size() << "\n";
    // rep(i,0,edges.size()) {
    //     cerr << edges[i][0] << " " << edges[i][1] << " " << edges[i][2] << "\n";
    // }

    //

    // DSU

    _size.assign(nn, 1);
    pars.assign(nn, -1);
    rep(i,0,nn) {
        pars[i] = i;
    }

    // go
    ans.assign(m, "");

    int jj = 0;

    rep(i,0,m)
    {
        while (jj < edges.size())
        {
            if (edges[jj][0] < visitors[i][0]) {
                union_sets(edges[jj][1], edges[jj][2]);
                jj++;
            }
            else break;
        }
        // visitors // 6 cases // check reach hörn
        int ind = visitors[i][2];
        find_par(0);
        find_par(1);
        find_par(2);
        find_par(3);
        if (visitors[i][1] == 1)
        {
            // clog << "1\n";
            ans[ind].pb('1');
            if (pars[0] != pars[1] && pars[1] != pars[2] && pars[1] != pars[3]) ans[ind].pb('2');
            if (pars[0] != pars[1] && pars[1] != pars[3] && pars[2] != pars[3] && pars[0] != pars[2]) ans[ind].pb('3');
            if (pars[0] != pars[1] && pars[0] != pars[2] && pars[0] != pars[3]) ans[ind].pb('4');
        }
        if (visitors[i][1] == 2)
        {
            // clog << "2\n";
            if (pars[0] != pars[1] && pars[1] != pars[2] && pars[1] != pars[3]) ans[ind].pb('1');
            ans[ind].pb('2');
            if (pars[2] != pars[1] && pars[3] != pars[2] && pars[2] != pars[0]) ans[ind].pb('3');
            if (pars[0] != pars[3] && pars[1] != pars[3] && pars[2] != pars[1] && pars[0] != pars[2]) ans[ind].pb('4');
        }
        if (visitors[i][1] == 3)
        {
            if (pars[0] != pars[1] && pars[1] != pars[3] && pars[2] != pars[3] && pars[0] != pars[2]) ans[ind].pb('1');
            if (pars[2] != pars[1] && pars[3] != pars[2] && pars[2] != pars[0]) ans[ind].pb('2');
            ans[ind].pb('3');
            if (pars[2] != pars[3] && pars[3] != pars[0] && pars[1] != pars[3]) ans[ind].pb('4');
        }
        if (visitors[i][1] == 4)
        {
            if (pars[0] != pars[1] && pars[0] != pars[2] && pars[0] != pars[3]) ans[ind].pb('1');
            if (pars[0] != pars[3] && pars[1] != pars[3] && pars[2] != pars[1] && pars[0] != pars[2]) ans[ind].pb('2');
            if (pars[2] != pars[3] && pars[3] != pars[0] && pars[1] != pars[3]) ans[ind].pb('3');
            ans[ind].pb('4');
        }
    }

    // cerr << "\n";

    rep(i,0,m) {
        cout << ans[i] << "\n";
    }
}

Compilation message

park.cpp: In function 'int32_t main()':
park.cpp:119:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         while (jj < edges.size())
      |                ~~~^~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 51124 KB Output is correct
2 Correct 243 ms 51384 KB Output is correct
3 Correct 240 ms 50116 KB Output is correct
4 Correct 246 ms 50628 KB Output is correct
5 Correct 245 ms 50472 KB Output is correct
6 Correct 244 ms 51116 KB Output is correct
7 Correct 234 ms 50572 KB Output is correct
8 Correct 224 ms 51892 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8648 KB Output is correct
2 Correct 33 ms 8024 KB Output is correct
3 Correct 32 ms 8272 KB Output is correct
4 Correct 32 ms 8176 KB Output is correct
5 Correct 31 ms 7756 KB Output is correct
6 Correct 33 ms 8092 KB Output is correct
7 Correct 31 ms 7520 KB Output is correct
8 Correct 35 ms 7460 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 51124 KB Output is correct
2 Correct 243 ms 51384 KB Output is correct
3 Correct 240 ms 50116 KB Output is correct
4 Correct 246 ms 50628 KB Output is correct
5 Correct 245 ms 50472 KB Output is correct
6 Correct 244 ms 51116 KB Output is correct
7 Correct 234 ms 50572 KB Output is correct
8 Correct 224 ms 51892 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 32 ms 8648 KB Output is correct
12 Correct 33 ms 8024 KB Output is correct
13 Correct 32 ms 8272 KB Output is correct
14 Correct 32 ms 8176 KB Output is correct
15 Correct 31 ms 7756 KB Output is correct
16 Correct 33 ms 8092 KB Output is correct
17 Correct 31 ms 7520 KB Output is correct
18 Correct 35 ms 7460 KB Output is correct
19 Correct 274 ms 58148 KB Output is correct
20 Correct 274 ms 58708 KB Output is correct
21 Correct 279 ms 58956 KB Output is correct
22 Correct 274 ms 58824 KB Output is correct
23 Correct 273 ms 58680 KB Output is correct
24 Correct 264 ms 58284 KB Output is correct