Submission #658960

#	Time	Username	Problem	Language	Result	Execution time	Memory
658960		victor_gao	Park (BOI16_park)	C++17	0 / 100	302 ms	52920 KiB

park

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 2015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct dsu{
    int boss[N],sz[N];
    void init(int n){
        for (int i=0;i<=n+5;i++){
            boss[i]=i; sz[i]=1;
        }
    }
    int find(int x){
        if (boss[x]==x) return x;
        return boss[x]=find(boss[x]);
    }
    void Merge(int a,int b){
        int ra=find(a),rb=find(b);
        if (ra==rb) return;
        if (sz[ra]<sz[rb]) swap(ra,rb);
        boss[rb]=ra;
        sz[ra]+=sz[rb];
    }
}d;
/*
左側 n+1, 右側 n+2, 上面 n+3, 下面 n+4
(0,0)


                (w,h) 
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
int n,m,w,h,r[N],vis[6];
string ans[100015];
vector<int>g[6];
vector<pair<double,pii> >edge;
vector<pair<int,pii> >people;
pii pos[N];
double count(int i,int j){
    return sqrt(1.0*(pos[i].x-pos[j].x)*(pos[i].x-pos[j].x)+1.0*(pos[i].y-pos[j].y)*(pos[i].y-pos[j].y))-r[i]-r[j];
}
int check(int x){
    return (d.find(x)==d.find(n+1))+(d.find(x)==d.find(n+2))+(d.find(x)==d.find(n+3))+(d.find(x)==d.find(n+4))-1;
}
void dfs(int p){
    if (vis[p]) return;
    vis[p]=1;
    for (auto i:g[p])
        dfs(i);
}
string count_ans(int start){
    for (int i=0;i<5;i++){
        vis[i]=0;
        g[i].clear();
    }
    if (!check(n+1)){
        g[1].push_back(4);
        g[4].push_back(1);
    }
    if (!check(n+2)){
        g[2].push_back(3);
        g[3].push_back(2);
    }
    if (!check(n+4)){
        g[1].push_back(2);
        g[2].push_back(1);
    }
    if (!check(n+3)){
        g[4].push_back(3);
        g[3].push_back(4);
    }
    dfs(start);
    string tans="";
    for (int i=0;i<5;i++){
        if (vis[i]) tans=tans+(char)(i+'0');
    }
    return tans;
}
signed main(){
    fast
    cin>>n>>m>>h>>w;
    for (int i=1;i<=n;i++)
        cin>>pos[i].y>>pos[i].x>>r[i];
    d.init(n);
    for (int i=1;i<=m;i++){
        int r,e; cin>>r>>e;
        people.push_back({r,{e,i}});
    }
    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            double dis=count(i,j);
            edge.push_back({dis,{i,j}});
        }
    }
    for (int i=1;i<=n;i++){
        edge.push_back({pos[i].x-r[i],{i,n+3}});
        edge.push_back({pos[i].y-r[i],{i,n+1}});
        edge.push_back({w-pos[i].x-r[i],{i,n+4}});
        edge.push_back({h-pos[i].y-r[i],{i,n+2}});
    }
    sort(people.begin(),people.end());
    sort(edge.begin(),edge.end());
    int p=0;
    for (auto i:edge){
        while (p<m&&2*people[p].x<=i.x){
            int st=people[p].y.x;
            ans[people[p].y.y]=count_ans(st);
            p++;
        }
        d.Merge(i.y.x,i.y.y);
    }
    for (int i=1;i<=m;i++)
        cout<<ans[i]<<"\n";
}

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