oj.uz

답안 #1053152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053152 2024-08-11T09:14:04 Z MercubytheFirst 분수 공원 (IOI21_parks) C++17
0 / 100
 1 ms 348 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);


struct Road
{
    pair<int, int> u, v, bench;
    int u_idx, v_idx, idx;
    int o;
    Road() {
        u = v = bench = {-1, -1};
        u_idx = v_idx = idx = o = -1;
    }
    Road(const pii& a, const pii& b, int a_idx, int b_idx, int j) : u(a), v(b), u_idx(a_idx), v_idx(b_idx), idx(j) {
        bench = {-1, -1};
        if(u > v) {
            swap(u, v);
            swap(u_idx, v_idx);
        }
        assert(u.first == v.first or u.second == v.second);
        if(u.first == v.first) { // vertical
            o = 0;
        }
        else { // horizontal
            o = 1;
        }
    }
    bool operator<(const Road& other) const {
        return make_pair(u, v) < make_pair(other.u, other.v);
    }
};

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    // vector<pii> points(n);
    // for(int i = 0; i < n; ++i) {
    //     points[i] = {x[i], y[i]};
    // }
    vector<bool> vis(n);
    map<pair<int, int>, int> mp;
    for(int i = 0; i < n; ++i) {
        mp[{x[i], y[i]}] = i;
    }
    const int dx[] = {0, +2, 0, -2},
              dy[] = {+2, 0, -2, 0};
    vector<Road> roads;
    auto road_dfs = [&](auto&& dfs, int i, int j) -> void
    {
        const int idx = mp[{i, j}];
        if(vis[idx])  {
            return;
        }
        vis[idx] = true;
        for(int d = 0; d < 4; ++d) {
            const int ii = i + dx[d], jj = j + dy[d];
            auto it = mp.find({ii, jj});
            if(it != mp.end() and !vis[it->second]) {
                roads.push_back(Road({i,j}, {ii,jj}, idx, it->second, roads.size()));
                dfs(dfs, ii, jj);
            }
        }
    };
    road_dfs(road_dfs, x[0], y[0]);
    // cout << roads << endl;
    assert((int)roads.size() < n);
    if((int)roads.size() != n - 1) {
        return 0;
    }
    sort(roads.begin(), roads.end());
    // for(const auto& x : roads) {
    //     cout << x.u << " -> " << x.v << endl;
    // }
    map<pair<int, int>, int> taken;
    const int bx[2][2] = {{-1, +1}, {-1, +1}};
    for(int i = 0; i < (int)roads.size(); ++i) {
        const Road& r = roads[i];
        array<int, 2> co{(r.u.first + r.v.first)/2, (r.u.second + r.u.second) / 2};
        co[r.o] -= 1;
        if(!taken.count({co[0], co[1]})) {
            taken[{co[0], co[1]}] = true;
            roads[i].bench = {co[0], co[1]};
            continue;
        }
        co[r.o] += 2;
        if(!taken.count({co[0], co[1]})) {
            taken[{co[0], co[1]}] = true;
            roads[i].bench = {co[0], co[1]};
        }
        else assert(false);
    }
    const int m = roads.size();
    vector<int> ansu(m), ansv(m), ansa(m), ansb(m);
    for(int i = 0; i < m; ++i) {
        ansu[roads[i].idx] = roads[i].u_idx;
        ansv[roads[i].idx] = roads[i].v_idx;
        ansa[roads[i].idx] = roads[i].bench.first;
        ansb[roads[i].idx] = roads[i].bench.second;
    }
    build(ansu, ansv, ansa, ansb);
    return 1;
}




template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}
 
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

/*
5
4 4
4 6
6 4
4 2
2 4


2
2 2
4 6
*/

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:88:15: warning: unused variable 'bx' [-Wunused-variable]
   88 |     const int bx[2][2] = {{-1, +1}, {-1, +1}};
      |               ^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB b[0] = 2 is not an odd integer
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB b[0] = 2 is not an odd integer
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB b[0] = 2 is not an odd integer
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB b[0] = 2 is not an odd integer
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB b[0] = 2 is not an odd integer
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB b[0] = 2 is not an odd integer
3 Halted 0 ms 0 KB -