Submission #440163

#	Time	Username	Problem	Language	Result	Execution time	Memory
440163		DanerZein	Fountain Parks (IOI21_parks)	C++17	5 / 100	485 ms	58388 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX_N=2e5+10;
vector<vi> G;
int pa[MAX_N],tam[MAX_N];
bool vis[MAX_N];
vector<ii> ox[MAX_N],oy[MAX_N];
void init(int n){
  for(int i=0;i<n;i++){
    pa[i]=i; tam[i]=1;
  }
}
int findset(int i){
  if(pa[i]==i) return i;
  return pa[i]=findset(pa[i]);
}
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;
    tam[v]+=tam[u];
  }
}
bool orden(iii a,iii b){
  if(a.second.second==b.second.second){
    return a.second.first<b.second.first;
  }
  return a.second.second<b.second.second;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
  int n=x.size();
  G.clear(); G.resize(n+1);
  for(int i=0;i<MAX_N;i++){
    ox[i].clear(); oy[i].clear();
  }
  memset(vis,0,sizeof vis);

  init(n);
  for(int i=0;i<n;i++){
    ox[x[i]].push_back(ii(y[i],i));
    oy[y[i]].push_back(ii(x[i],i));
  }
  for(int i=0;i<MAX_N;i++){
    sort(ox[i].begin(),ox[i].end());
    sort(oy[i].begin(),oy[i].end());
  }
  vector<int> ru,rv,ra,rb;
  int id=-1;
  for(int i=0;i<MAX_N;i++){
    int a,b;
    for(int j=0;j<ox[i].size();j++){
      if(j+1!=ox[i].size() && ox[i][j+1].first-ox[i][j].first==2){
	a=ox[i][j+1].second; b=ox[i][j].second;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
    for(int j=0;j<oy[i].size();j++){
      if(id==-1){
	id=oy[i][j].second;
      }
      if(j+1!=oy[i].size() && oy[i][j+1].first-oy[i][j].first==2){
	a=oy[i][j+1].second; b=oy[i][j].second;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
  }
  if(tam[findset(0)]!=n) return 0;
  queue<int> q; q.push(id);
  set<ii> ban;
  while(!q.empty()){
    int u; u=q.front();
    q.pop();
    vis[u]=1;
    vector<iii> pro;
    for(auto &v:G[u]){
      if(!vis[v]) pro.push_back(iii(v,ii(x[v],y[v])));
    }
    sort(pro.begin(),pro.end(),orden);
    for(int i=0;i<pro.size();i++){
      int a=pro[i].first;
      ru.push_back(a); rv.push_back(u);
      int xi,yi;
      if(x[a]==x[u]){
	xi=x[a]-1; yi=(y[a]+y[u])/2;
	if(ban.find(ii(xi,yi))!=ban.end()){
	  xi=x[a]+1;
	}
	ban.insert(ii(xi,yi));
      }
      else{
	xi=(x[a]+x[u])/2; yi=y[a]-1;
	if(ban.find(ii(xi,yi))!=ban.end()){
	  yi=y[a]+1;
	}
	ban.insert(ii(xi,yi));
      }
      ra.push_back(xi); rb.push_back(yi);
      q.push(a);
    }
  }
  build(ru,rv,ra,rb);
  return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:58: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]
   58 |     for(int j=0;j<ox[i].size();j++){
      |                 ~^~~~~~~~~~~~~
parks.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       if(j+1!=ox[i].size() && ox[i][j+1].first-ox[i][j].first==2){
      |          ~~~^~~~~~~~~~~~~~
parks.cpp:66: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]
   66 |     for(int j=0;j<oy[i].size();j++){
      |                 ~^~~~~~~~~~~~~
parks.cpp:70:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |       if(j+1!=oy[i].size() && oy[i][j+1].first-oy[i][j].first==2){
      |          ~~~^~~~~~~~~~~~~~
parks.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<pro.size();i++){
      |                 ~^~~~~~~~~~~

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