Submission #1066739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066739		vjudge1	Park (BOI16_park)	C++17	100 / 100	2131 ms	25164 KiB

park

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define fi first 
#define se second

using namespace std;

const int N = 2e3 + 3;

int n, m;
ll w, h;

vector<int> edge[N];
bool visited[N];

using pll = pair<ll, ll>;
using plll = pair<pair<ll, ll>, ll>;
vector<plll> circle(N);

int dv[] = {1, 0, -1, 0};
int dh[] = {0, 1, 0, -1};

ll qua(ll a){
    return a*a;
}

ll disQ(pair<ll, ll> loc1, pair<ll, ll> loc2){
    return qua(loc1.fi - loc2.fi) + qua(loc1.se - loc2.se);
}

bool ka(pair<pair<ll, ll>, ll> cir, ll r ){
    return h - cir.fi.se < cir.se + 2*r;
}

bool kb(pair<pair<ll, ll>, ll> cir, ll r){
    return cir.fi.se < cir.se + 2*r;
}

bool kkr(pair<pair<ll, ll>, ll> cir, ll r){
    return cir.fi.fi < cir.se + 2*r;
}

bool kkn(pair<pair<ll, ll>, ll> cir, ll r){
    return w - cir.fi.fi < cir.se + 2*r;
}


ll ver(){
    ll l = 0, r = 1e9;
    while(l <= r){
        ll md = (l + r)/2;
        for(int i = 0; i < n; i++){
            edge[i].clear();
            visited[i] = false;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(disQ(circle[i].fi, circle[j].fi) < qua(circle[i].se + circle[j].se + 2*md)){
                    edge[i].push_back(j);
                    edge[j].push_back(i);
                }
            }
        }

        bool tutup = false;
        for(int i = 0; i < n; i++){
            if(!visited[i] && kkr(circle[i], md)){
                stack<int> st;
                st.push(i);
                while(!st.empty()){
                    int v = st.top();

                    st.pop();
                    if(!visited[v]){
                        if(kkn(circle[v], md)){
                            tutup = true;
                        }
                        visited[v] = true;
                        for(auto u: edge[v]){
                            st.push(u);
                        }
                    }
                }
            }
        }
        if(tutup){
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    return r;
}

ll a(){
    ll l = 0, r = 1e9;
    while(l <= r){
        ll md = (l + r)/2;
        for(int i = 0; i < n; i++){
            edge[i].clear();
            visited[i] = false;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(disQ(circle[i].fi, circle[j].fi) < qua(circle[i].se + circle[j].se + 2*md)){
                    edge[i].push_back(j);
                    edge[j].push_back(i);
                }
            }
        }

        bool tutup = false;
        for(int i = 0; i < n; i++){
            if(!visited[i] && ka(circle[i], md)){
                stack<int> st;
                st.push(i);
                while(!st.empty()){
                    int v = st.top();

                    st.pop();
                    if(!visited[v]){
                        if(kkr(circle[v], md)){
                            tutup = true;
                        }
                        visited[v] = true;
                        for(auto u: edge[v]){
                            st.push(u);
                        }
                    }
                }
            }
        }
        if(tutup){
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    return r;
}

ll b(){
    ll l = 0, r = 1e9;
    while(l <= r){
        ll md = (l + r)/2;
        for(int i = 0; i < n; i++){
            edge[i].clear();
            visited[i] = false;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(disQ(circle[i].fi, circle[j].fi) < qua(circle[i].se + circle[j].se + 2*md)){
                    edge[i].push_back(j);
                    edge[j].push_back(i);
                }
            }
        }

        bool tutup = false;
        for(int i = 0; i < n; i++){
            if(!visited[i] && ka(circle[i], md)){
                stack<int> st;
                st.push(i);
                while(!st.empty()){
                    int v = st.top();

                    st.pop();
                    if(!visited[v]){
                        if(kkn(circle[v], md)){
                            tutup = true;
                        }
                        visited[v] = true;
                        for(auto u: edge[v]){
                            st.push(u);
                        }
                    }
                }
            }
        }
        if(tutup){
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    return r;
}

ll c(){
    ll l = 0, r = 1e9;
    while(l <= r){
        ll md = (l + r)/2;
        for(int i = 0; i < n; i++){
            edge[i].clear();
            visited[i] = false;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(disQ(circle[i].fi, circle[j].fi) < qua(circle[i].se + circle[j].se + 2*md)){
                    edge[i].push_back(j);
                    edge[j].push_back(i);
                }
            }
        }

        bool tutup = false;
        for(int i = 0; i < n; i++){
            if(!visited[i] && kb(circle[i], md)){
                stack<int> st;
                st.push(i);
                while(!st.empty()){
                    int v = st.top();

                    st.pop();
                    if(!visited[v]){
                        if(kkr(circle[v], md)){
                            tutup = true;
                        }
                        visited[v] = true;
                        for(auto u: edge[v]){
                            st.push(u);
                        }
                    }
                }
            }
        }
        if(tutup){
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    return r;
}

ll d(){
    ll l = 0, r = 1e9;
    while(l <= r){
        ll md = (l + r)/2;
        for(int i = 0; i < n; i++){
            edge[i].clear();
            visited[i] = false;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(disQ(circle[i].fi, circle[j].fi) < qua(circle[i].se + circle[j].se + 2*md)){
                    edge[i].push_back(j);
                    edge[j].push_back(i);
                }
            }
        }

        bool tutup = false;
        for(int i = 0; i < n; i++){
            if(!visited[i] && kb(circle[i], md)){
                stack<int> st;
                st.push(i);
                while(!st.empty()){
                    int v = st.top();

                    st.pop();
                    if(!visited[v]){
                        if(kkn(circle[v], md)){
                            tutup = true;
                        }
                        visited[v] = true;
                        for(auto u: edge[v]){
                            st.push(u);
                        }
                    }
                }
            }
        }
        if(tutup){
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    return r;
}

ll hor(){
    ll l = 0, r = 1e9;
    while(l <= r){
        ll md = (l + r)/2;
        for(int i = 0; i < n; i++){
            edge[i].clear();
            visited[i] = false;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(disQ(circle[i].fi, circle[j].fi) < qua(circle[i].se + circle[j].se + 2*md)){
                    edge[i].push_back(j);
                    edge[j].push_back(i);
                }
            }
        }

        bool tutup = false;
        for(int i = 0; i < n; i++){
            if(!visited[i] && ka(circle[i], md)){
                stack<int> st;
                st.push(i);
                while(!st.empty()){
                    int v = st.top();

                    st.pop();
                    if(!visited[v]){
                        if(kb(circle[v], md)){
                            tutup = true;
                        }
                        visited[v] = true;
                        for(auto u: edge[v]){
                            st.push(u);
                        }
                    }
                }
            }
        }
        if(tutup){
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    return r;
}


void solve(){
    cin >> n >> m; 
    cin >> w >> h;
    for(int i = 0; i < n; i++){
        cin >> circle[i].fi.fi >> circle[i].fi.se >> circle[i].se;
    }


    ll verti = ver();
    ll hori = hor();
    ll at = a();
    ll bt = b();
    ll ct = c();
    ll dt = d();
    ll r, e;
    int nilai[3][3] = {
        {4, 0, 3},
        {0, 0, 0},
        {1, 0, 2}
    };
    map<int, pair<int, int>> loc;
    loc[4] = {0, 0};
    loc[3] = {0, 2};
    loc[1] = {2, 0};
    loc[2] = {2, 2};
    for(int i = 0; i < m; i++){
        cin >> r >> e;
        vector<int> res;
        vector<vector<bool>> batas(3, vector<bool>(3, 0));
        vector<vector<bool>> visited(3, vector<bool>(3, 0));
        queue<int> q;

        if(r > verti){
            batas[1][0] = batas[1][1] = batas[1][2] = true;
        }
        if(r > hori){
            batas[0][1] = batas[1][1] = batas[2][1] = true;
        }
        if(r > at){
            batas[0][0] = true;
        }
        if(r > bt){
            batas[0][2] = true;
        }
        if(r > ct){
            batas[2][0] = true;
        }
        if(r > dt){
            batas[2][2] = true;
        }
        stack<pair<int, int>> st;
        st.push(loc[e]);
        while(!st.empty()){
            int v = st.top().fi;
            int h = st.top().se;
            st.pop();
            if(nilai[v][h] != 0 && !visited[v][h]){
                res.push_back(nilai[v][h]);
            }
            if(!batas[v][h]){
                visited[v][h] = true;
                for(int j = 0; j < 4; j++){
                    int nv = v + dv[j];
                    int nh = h + dh[j];
                    if(nv >= 0 && nv < 3 && nh >= 0 && nh < 3 && !batas[nv][nh] && !visited[nv][nh]){
                        st.push({nv, nh});
                    }
                }

            }
        }
        sort(res.begin(), res.end());
        for(int j = 0; j < res.size(); j++){
            cout << res[j];
        }
        cout << endl;
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

park.cpp: In function 'void solve()':
park.cpp:404:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  404 |         for(int j = 0; j < res.size(); j++){
      |                        ~~^~~~~~~~~~~~

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