Submission #1276220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276220		tu2108	Park (BOI16_park)	C++20	27 / 100	219 ms	327680 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define getbit(x , i) ((x >> i) & 1)
typedef pair<int , int> pii;

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 2000;
const int maxm = 1e5;

int n , m , W , H;

int lab[maxn + 9];
bool checkrow[5][5] , checkcol[5][5];
vector<int> ans[maxm + 5];

struct circle{
    pii p;
    int r;
};
circle cc[maxn + 5];

struct edge{
    int u , v;
    double w;

    bool operator <(const edge &A){
        return w < A.w;
    }
};
vector<edge> e;

struct query{
    int r , c , id;

    bool operator <(const query &A){
        return r < A.r;
    }
};
query qr[maxm + 5];

double dis(const pii &p1 , const pii &p2){
    return sqrt((p2.fi - p1.fi) * (p2.fi - p1.fi) + (p2.se - p1.se) * (p2.se - p1.se));
}

int find(int u){
    if(lab[u] < 0) return u;
    else return lab[u] = find(lab[u]);;
}

void join(int u , int v){
    u = find(u) , v = find(v);

    if(u != v){
        if(lab[u] > lab[v]) swap(u , v);

        lab[u] += lab[v];
        lab[v] = u;
    }
}

main()
{
    faster
    cin >> n >> m >> W >> H;
    for(int i = 1 ; i <= n ; ++i) cin >> cc[i].p.fi >> cc[i].p.se >> cc[i].r;
    for(int i = 1 ; i <= m ; ++i){
        cin >> qr[i].r >> qr[i].c;
        qr[i].id = i;
    }

    for(int i = 1 ; i <= n ; ++i){
        e.pb({i , n + 1 , cc[i].p.fi - cc[i].r});
        e.pb({i , n + 2 , cc[i].p.se - cc[i].r});
        e.pb({i , n + 3 , W - cc[i].p.fi - cc[i].r});
        e.pb({i , n + 4 , H - cc[i].p.se - cc[i].r});

        for(int j = i + 1 ; j <= n ; ++j) e.pb({i , j , dis(cc[i].p , cc[j].p) - cc[i].r - cc[j].r});
    }

    sort(e.begin() , e.end());
    sort(qr + 1 , qr + 1 + m);

    for(int i = 1 ; i <= n + 4 ; ++i) lab[i] = -1;

    checkrow[1][2] = checkrow[2][1] = 1;
    checkrow[3][4] = checkrow[4][3] = 1;

    checkcol[1][4] = checkcol[4][1] = 1;
    checkcol[2][3] = checkcol[3][2] = 1;

    int ptr = 0;
    for(int i = 1 ; i <= m ; ++i){
        while(ptr < e.size() && e[ptr].w < (double)qr[i].r * 2){
            //if(i == 1) cout << e[ptr].u << " " << e[ptr].v << " " << e[ptr].w << endl;
            join(e[ptr].u , e[ptr].v);
            ++ptr;
        }

        ans[qr[i].id].pb(qr[i].c);

        int nxt = qr[i].c % n + 1;
        if(find(n + qr[i].c) == find(n + nxt)) continue;

        for(int j = 1 ; j <= 4 ; ++j){
            if(qr[i].c == j) continue;
            else{
                int nxt = j % 4 + 1;
                if(find(n + j) == find(n + nxt)) continue;

                if(find(n + 1) == find(n + 3)){
                    if(checkrow[qr[i].c][j]) ans[qr[i].id].pb(j);
                }
                else if(find(n + 2) == find(n + 4)){
                    if(checkcol[qr[i].c][j]) ans[qr[i].id].pb(j);
                }
                else ans[qr[i].id].pb(j);
            }
        }
    }

    for(int i = 1 ; i <= m ; ++i){
        sort(ans[i].begin() , ans[i].end());
        for(auto x : ans[i]) cout << x;
        cout << '\n';
    }
}

Compilation message (stderr)

park.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main()
      | ^~~~
park.cpp: In function 'int main()':
park.cpp:78:38: warning: narrowing conversion of '(cc[i].circle::p.std::pair<long long int, long long int>::first - cc[i].circle::r)' from 'long long int' to 'double' [-Wnarrowing]
   78 |         e.pb({i , n + 1 , cc[i].p.fi - cc[i].r});
      |                           ~~~~~~~~~~~^~~~~~~~~
park.cpp:79:38: warning: narrowing conversion of '(cc[i].circle::p.std::pair<long long int, long long int>::second - cc[i].circle::r)' from 'long long int' to 'double' [-Wnarrowing]
   79 |         e.pb({i , n + 2 , cc[i].p.se - cc[i].r});
      |                           ~~~~~~~~~~~^~~~~~~~~
park.cpp:80:42: warning: narrowing conversion of '((W - cc[i].circle::p.std::pair<long long int, long long int>::first) - cc[i].circle::r)' from 'long long int' to 'double' [-Wnarrowing]
   80 |         e.pb({i , n + 3 , W - cc[i].p.fi - cc[i].r});
      |                           ~~~~~~~~~~~~~~~^~~~~~~~~
park.cpp:81:42: warning: narrowing conversion of '((H - cc[i].circle::p.std::pair<long long int, long long int>::second) - cc[i].circle::r)' from 'long long int' to 'double' [-Wnarrowing]
   81 |         e.pb({i , n + 4 , H - cc[i].p.se - cc[i].r});
      |                           ~~~~~~~~~~~~~~~^~~~~~~~~

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