제출 #468561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468561		fun_day	분수 공원 (IOI21_parks)	C++17	5 / 100	1400 ms	77436 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

struct Edge {
  int from , to , cost;
  bool operator<(const Edge &autre){
    if(from == autre.from){
      return to < autre.to;
    }
    return from < autre.from;
  }
}; 

const int N = 1e5 * 2 + 10;
int p[N];
int sz[N];

void make(int a){
  p[a] = a;
  sz[a] = 1;
  return ;
}

int find_set(int a){
  if(p[a] == a) return a;
  return p[a] = find_set(p[a]);
}

bool union_sets(int a , int b){
  a = find_set(a);
  b = find_set(b);
  if(a == b) return false;
  if(sz[a] < sz[b]) swap(a,b);
  p[b] = a;
  sz[a] += sz[b];
  return true;
}

const int dx[4] = {2 , 0 , 0 , -2} , dy[4] = {0 , 2 , -2 , 0};

int construct_roads(vector<int> x , vector<int> y){
  int n = (int)x.size();
  if(n == 1){
    build({} , {} , {} , {});
    return 1;
  }
  map<pair<int,int> , int> seen;
  map<int , pair<int,int>> after;
  for(int i = 0 ; i < n ; i++){
    seen[make_pair(x[i] , y[i])] = i + 1;
    after[i] = make_pair(x[i] , y[i]);
  }
  for(int i = 0 ; i < n ; i++){
    make(i);
  }
  vector<int> u  , q;
  for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < 4 ; j++){
      int new_x = x[i] + dx[j];
      int new_y = y[i] + dy[j];
      int m = seen[make_pair(new_x , new_y)];
      if(m){
        m--;
        if(union_sets(i , m)){
          u.emplace_back(i);
          q.emplace_back(m);          
        }
      }
    }
  }
  if(sz[find_set(0)] != n) return 0;
  map<pair<int,int> , bool> used;
  vector<int> one , two;
  for(int i = 0 ; i < (int)u.size() ; i++){
    int now_t = u[i] , now_z = q[i];
    auto pq = after[now_t] , r = after[now_z];
    pair<int,int> choice1 , choice2;
    if(pq.first == r.first){
      choice1 = make_pair(pq.first - 1 , (pq.second+r.second)/2);
      choice2 = make_pair(pq.first + 1 , (pq.second+r.second)/2);
    }
    else{
      assert(pq.second == r.second);
      choice1 = make_pair((pq.first + r.first)/2 , pq.second - 1);
      choice2 = make_pair((pq.first + r.first) / 2 , pq.second + 1);
    }
    if(!used[choice1]){
      one.emplace_back(choice1.first);
      two.emplace_back(choice1.second);
      used[choice1] = true;
    }
    else if(!used[choice2]){
      one.emplace_back(choice2.first);
      two.emplace_back(choice2.second);
      used[choice2] = true;      
    }
  }
  build(u , q , one , two);
  return 1;
}
/*int main(){
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  for(int i = 0 ; i < n ; i++){
    cin >> x[i];
  }
  for(int i = 0 ; i < n ; i++){
    cin >> y[i];
  }
  cout << construct_roads(x , y);
  return 0;
} */

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