Submission #1192791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192791		Godgift42	Park (BOI16_park)	C++20	0 / 100	501 ms	49776 KiB

park

#include <bits/stdc++.h>
using namespace std;

vector<int> rt;
vector<int> sz;

int find(int u){
  if(u!=rt[u])rt[u]=find(rt[u]);
  return rt[u];
}

void unite(int u, int v){
  u=find(u);
  v=find(v);
  if(u!=v){
    if(sz[u]>sz[v]){
      rt[v]=u;
      sz[u]+=sz[v];
    }
    else{
      rt[u]=v;
      sz[v]+=sz[u];
    }
  }
}

int main(){
  int n,m;
  cin >> n >> m;
  int w,h;
  cin >> w >> h;
  vector<vector<int>>tr(n,vector<int>(3));
  for(int i=0;i<n;i++){
    cin >> tr[i][0] >> tr[i][1] >> tr[i][2];
  }
  vector<pair<int,pair<int,int>>> p(m);
  for(int i=0;i<m;i++){
    cin >> p[i].first >> p[i].second.first;
    p[i].second.second=i;
  }
  vector<pair<int,pair<int,int>>> el;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j)continue;
      int d=(int)(sqrt((tr[i][0]-tr[j][0])*(tr[i][0]-tr[j][0])+(tr[i][1]-tr[j][1])*(tr[i][1]-tr[j][1]))-tr[i][2]-tr[j][2]);
      el.push_back({d,{i,j}});
    }
    int d=(int)(tr[i][1]-tr[i][2]);
    el.push_back({d,{i,n}});
    d=(int)(w-tr[i][0]-tr[i][2]);
    el.push_back({d,{i,n+1}});
    d=(int)(h-tr[i][1]-tr[i][2]);
    el.push_back({d,{i,n+2}});
    d=(int)(tr[i][0]-tr[i][2]);
    el.push_back({d,{i,n+3}});
  }
  sort(el.begin(),el.end());
  
  rt.resize(n+4);
  for(int i=0;i<n+4;i++)rt[i]=i;
  sz.resize(n+4,1);
  sort(p.begin(),p.end());
  vector<vector<int>> ans(m);
  int j=0;
  for(int i=0;i<m;i++){
    while(j<el.size() and el[j].first<2*p[i].first){
      unite(el[j].second.first,el[j].second.second);
      j++;
    }
    ans[p[i].second.second].push_back(p[i].second.first);
    if(p[i].second.first==1){
      if(find(n)==find(n+3))continue;
      if(find(n+1)!=find(n+3) and find(n+2)!=find(n+3))ans[p[i].second.second].push_back(4);
      if(find(n+1)!=find(n) and find(n+2)!=find(n))ans[p[i].second.second].push_back(2);
      if(find(n+1)!=find(n+2) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(3);
    }
    else if(p[i].second.first==2){
      if(find(n+1)==find(n))continue;
      if(find(n+1)!=find(n+2) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(3);
      if(find(n+3)!=find(n) and find(n+2)!=find(n))ans[p[i].second.second].push_back(1);
      if(find(n+3)!=find(n+2) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(4);
    }
    else if(p[i].second.first==3){
      if(find(n+1)==find(n+2))continue;
      if(find(n+1)!=find(n+3) and find(n)!=find(n+1))ans[p[i].second.second].push_back(2);
      if(find(n+2)!=find(n+3) and find(n+2)!=find(n))ans[p[i].second.second].push_back(4);
      if(find(n)!=find(n+3) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(1);
    }
    else{
      if(find(n+2)==find(n+3))continue;
      if(find(n+1)!=find(n+3) and find(n)!=find(n+3))ans[p[i].second.second].push_back(1);
      if(find(n+1)!=find(n+2) and find(n+2)!=find(n))ans[p[i].second.second].push_back(3);
      if(find(n+1)!=find(n) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(2);
    }
  }
  for(int i=0;i<m;i++){
    sort(ans[i].begin(),ans[i].end());
    for(auto o:ans[i])cout <<o;
    cout << "\n";
  }
}

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