Submission #862872

#	Time	Username	Problem	Language	Result	Execution time	Memory
862872		Ellinor	Park (BOI16_park)	C++14	100 / 100	279 ms	58956 KiB

park

#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 (stderr)

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42