Submission #435646

#	Time	Username	Problem	Language	Result	Execution time	Memory
435646		DanerZein	Fountain Parks (IOI21_parks)	C++17	15 / 100	373 ms	48544 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vi;
const int MAX_N=2e5+10;
vector<vi> ox(MAX_N),oy(MAX_N);
int pa[MAX_N],tam[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];
  }
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
  int n=x.size();
  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;
  set<ii> ba;
  init(n);
  for(int i=2;i<MAX_N;i+=2){
    bool sw=0;
    int t=oy[i].size();
    for(int j=0;j<t-1;j++){
      int xi=oy[i][j].first,xj=oy[i][j+1].first;
      int u=oy[i][j].second,v=oy[i][j+1].second;
      if(xj-xi==2){
	ru.push_back(oy[i][j].second);
	rv.push_back(oy[i][j+1].second);
	unionset(u,v);
	if(sw){
	  ra.push_back(xi+1); rb.push_back(i-1);
	  ba.insert(ii(xi+1,i-1));
	}
	else{
	  ra.push_back(xi+1); rb.push_back(i+1);
	  ba.insert(ii(xi+1,i+1));
	}
	sw^=1;
      }
    }
  }
  for(int i=2;i<MAX_N;i+=2){
    int t=ox[i].size();
    for(int j=0;j<t-1;j++){
      int yi=ox[i][j].first,yj=ox[i][j+1].first;
      int u=ox[i][j].second,v=ox[i][j+1].second;
      if(yj-yi==2){
	ru.push_back(u); rv.push_back(v);
	unionset(u,v);
	if(ba.find(ii(i-1,yi+1))!=ba.end()){
	  ra.push_back(i+1); rb.push_back(yi+1);
	  ba.insert(ii(i+1,yi+1));
	}
	else{
	  ra.push_back(i-1); rb.push_back(yi+1);
	  ba.insert(ii(i-1,yi+1));
	}
      }
    }
  }
  if(tam[findset(0)]!=n) return 0;
  build(ru,rv,ra,rb);
  return 1;
}

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