oj.uz

답안 #468518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468518 2021-08-28T15:55:16 Z fun_day 분수 공원 (IOI21_parks) C++17
0 / 100
 0 ms 204 KB 
#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] = 0;
  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();
  vector<Edge> v;
  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++){
    v.push_back({x[i] , y[i] , i});
  }
  for(int i = 0 ; i < n ; i++){
    make(i);
  }
  sort(v.begin(), v.end());
  // first we see if an answer exists
  vector<int> u  , q;
  for(int i = 0 ; i < n ; i++){
    bool ok = false;
    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--;
        ok = true;
        if(union_sets(i , m)){
          u.emplace_back(i);
          q.emplace_back(m);          
        }
      }
    }
    if(!ok) 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]){
      assert(!used[choice2]);
      one.emplace_back(choice2.first);
      two.emplace_back(choice2.second);
    }
    else{
      assert(!used[choice1]);
      one.emplace_back(choice1.first);
      two.emplace_back(choice1.second);
    }
  }
  build(u , q , one , two);
  //debug(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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -