Submission #614378

#	Time	Username	Problem	Language	Result	Execution time	Memory
614378		DanerZein	Fountain Parks (IOI21_parks)	C++17	70 / 100	1372 ms	114724 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
const int MAX_N=2e5+10;
struct point{
  int x,y,id;
  point(int xx,int yy,int ii){
    x=xx;
    y=yy;
    id=ii;
  }
  ii coord(){
    return ii(x,y);
  }
};
struct Road{
  int u,v,id;
  bool hor;
  Road(int uu,int vv,int ii,bool h){
    u=uu; v=vv; id=ii; hor=h;
  }
};
int pa[MAX_N];
int n;
vector<point> foun;
vector<Road> road;
int X[5]={0,1,0,-1};
int Y[5]={-1,0,1,0};
int ns=0;
void init(int n){
  for(int i=0;i<n;i++) pa[i]=i;
  ns=n;
}
int findset(int u){
  return pa[u]==u?u:pa[u]=findset(pa[u]);
}
bool issameset(int i,int j){
  return findset(i)==findset(j);
}
void unionset(int i,int j){
  if(!issameset(i,j)){
    int u=findset(i),v=findset(j);
    pa[u]=v;
    ns--;
  }
}
set<ii> us;
vector<ii> puntosChoque(int id){
  vector<ii> pu;
  ii f1=foun[road[id].u].coord();
  ii f2=foun[road[id].v].coord();
  int x,y;
  if(f1.second==f2.second){
    x=(f1.first+f2.first)/2;
    y=f1.second;
  }
  else{
    x=f1.first;
    y=(f1.second+f2.second)/2;
  }
  for(int i=0;i<4;i++){
    int xk=x+X[i];
    int yk=y+Y[i];
    if(us.find(ii(xk,yk))!=us.end()) continue;
    if(ii(xk,yk)!=f1 && ii(xk,yk)!=f2)
      pu.push_back(ii(xk,yk));
  }
  return pu;
}
bool canConnect(point u,point v){
  return !issameset(u.id,v.id) && (((u.x==v.x && abs(u.y-v.y)==2)) || ((u.y==v.y && abs(u.x-v.x)==2)));
}
bool don[MAX_N];
bool sortX(point a,point b){
  return a.x!=b.x ? a.x<b.x: a.y<b.y;
}
bool sortY(point a,point b){
  return a.y!=b.y ? a.y<b.y : a.x<b.x;
}
bool origin(point a,point b){
  return a.id<b.id;
}
int be;
map<ii,int> punid;
map<int,ii> idpun;
map<int,vi> conbe;
void choque(int id){
  vector<ii> pu=puntosChoque(id);
  for(int i=0;i<pu.size();i++){
    if(punid.find(pu[i])==punid.end()){
      punid[pu[i]]=be;
      idpun[id]=pu[i];
      be++;
    }
    conbe[punid[pu[i]]].push_back(id);
  }
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
  n=x.size();
  for(int i=0;i<n;i++){
    foun.push_back(point(x[i],y[i],i));
  }
  init(n);
  sort(foun.begin(),foun.end(),sortX);
  vector<int> ua,va;
  for(int i=0;i<n-1;i++){
    if(canConnect(foun[i],foun[i+1])){
      unionset(foun[i].id,foun[i+1].id);
      ua.push_back(foun[i].id);
      va.push_back(foun[i+1].id);
      road.push_back(Road(foun[i].id,foun[i+1].id,road.size(),0));
    }
  }
  sort(foun.begin(),foun.end(),sortY);
  for(int i=0;i<n-1;i++){
    if(canConnect(foun[i],foun[i+1])){
      unionset(foun[i].id,foun[i+1].id);
      ua.push_back(foun[i].id);
      va.push_back(foun[i+1].id);  
      road.push_back(Road(foun[i].id,foun[i+1].id,road.size(),1));
    }
  }
  sort(foun.begin(),foun.end(),origin);
  if(ns!=1) return 0;
  be=road.size();
  for(int i=0;i<road.size();i++) choque(i);
  priority_queue<ii, vector<ii>, greater<ii> > pq;
  for(int i=0;i<road.size();i++){
    int pro=0;
    vector<ii> pu=puntosChoque(i);
    for(int j=0;j<pu.size();j++){
      int v=punid[pu[j]];
      pq.push(ii(conbe[v].size(),i));
    }
  }
  /*for(int i=0;i<road.size();i++){
    cout<<road[i].u<<" "<<road[i].v<<endl;
  }*/
  int t=road.size();
  vector<int> a(t),b(t);
  while(!pq.empty()){
    int i=pq.top().second;
    pq.pop();
    if(don[i]) continue;
    vector<ii> pu=puntosChoque(i);
    if(pu.empty()) return 0;
    int iu=0;
    //cout<<i<<": \n";
    for(int j=0;j<pu.size();j++){
      int u=punid[pu[j]];
      int vis=0;
      //cout<<pu[j].first<<" "<<pu[j].second<<":\n";
      for(auto &v:conbe[u]){
	//	cout<<v<<endl;
	if(!don[v]) vis++;
      }
      if(vis==1){
	iu=j;
	break;
      }
    }
    don[i]=1;
    // cout<<endl;
    us.insert(pu[iu]);
    a[i]=pu[iu].first; b[i]=pu[iu].second;
    for(int j=0;j<pu.size();j++){
      int vis=0;
      int u=punid[pu[j]];
      int id=-1;
      for(auto &v:conbe[u]){
	if(!don[v]){
	  id=v;
	  vis++;
	}
      }
      if(vis==1){
	pq.push(ii(1,id));
      }
    }
  }
  build(ua,va,a,b);
  return 1;
}

Compilation message (stderr)

parks.cpp: In function 'void choque(int)':
parks.cpp:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int i=0;i<pu.size();i++){
      |               ~^~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:129:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for(int i=0;i<road.size();i++) choque(i);
      |               ~^~~~~~~~~~~~
parks.cpp:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for(int i=0;i<road.size();i++){
      |               ~^~~~~~~~~~~~
parks.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int j=0;j<pu.size();j++){
      |                 ~^~~~~~~~~~
parks.cpp:132:9: warning: unused variable 'pro' [-Wunused-variable]
  132 |     int pro=0;
      |         ^~~
parks.cpp:152:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int j=0;j<pu.size();j++){
      |                 ~^~~~~~~~~~
parks.cpp:169:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     for(int j=0;j<pu.size();j++){
      |                 ~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30