Submission #660329

#	Time	Username	Problem	Language	Result	Execution time	Memory
660329		600Mihnea	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	3566 ms	6548 KiB

skyscrapers

bool home = 0;
#include <bits/stdc++.h>

using namespace std;

struct T
{
  int x;
  int y;
};

bool operator < (T a, T b)
{
  if (a.x != b.x)
  {
    return a.x < b.x;
  }
  return a.y < b.y;
}

const int N = 150000 + 7;
int n;
int task;
T points[N];
map<T, int> w;
bool vis[N];
int dirx[] = {-1, 0, 1, 0};
int diry[] = {0, 1, 0, -1};
int solution[N];
bool ales_deja[N];

bool sanity_check()
{
  int who = -1, cnt = 0;
  for (int i = 1; i <= n; i++)
  {
    vis[i] = 0;
    if (ales_deja[i])
    {
      continue;
    }
    who = i;
    cnt++;
  }
  if (cnt == 0)
  {
    return 1;
  }
  vector<int> q = {who};
  vis[who] = 1;
  for (int i = 0; i < (int) q.size(); i++)
  {
    int a = q[i];
    for (int dx = -1; dx <= +1; dx++)
    {
      for (int dy = -1; dy <= +1; dy++)
      {
        T nw = {points[a].x + dx, points[a].y + dy};
        if (w.count(nw))
        {
          int b = w[nw];
          if (ales_deja[b])
          {
            continue;
          }
          if (vis[b] == 0)
          {
            vis[b] = 1;
            q.push_back(b);
          }
        }
      }
    }
  }
  if ((int) q.size() < cnt)
  {
    return 0;
  }
  assert((int) q.size() == cnt);
  return 1;
}

int main()
{
  if (home == 0)
  {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  }
  else
  {
    freopen ("input.txt", "r", stdin);
  }

  cin >> n >> task;
  assert(task == 1 || task == 2);

  for (int i = 1; i <= n; i++)
  {
    cin >> points[i].x >> points[i].y;
    w[points[i]] = i;
  }

  {
    /// Just run a quick BFS to check whether or not the answer is NO
    if (!sanity_check())
    {
      cout << "NO\n";
      return 0;
    }

  }

  map<T, int> ids;
  vector<int> t;
  vector<int> ext_tag;

  function<int(int)> get_inner_root = [&] (int a)
  {
    if (t[a] == a)
    {
      return a;
    }
    else
    {
      return t[a] = get_inner_root(t[a]);
    }
  };

  function<int(T)> get_root = [&] (T a)
  {
    if (!ids.count(a))
    {
      ids[a] = (int) t.size();
      t.push_back((int) t.size());
      ext_tag.push_back(0);
    }
    return get_inner_root(ids[a]);
  };

  function<void(T, T)> join = [&] (T x, T y)
  {
    int a = get_root(x);
    int b = get_root(y);
    if (a == b)
    {
      return;
    }
    t[a] = b;
    ext_tag[b] |= ext_tag[a];
  };




  for (int i = 1; i <= n; i++)
  {
    for (int dx = -1; dx <= +1; dx++)
    {
      for (int dy = -1; dy <= +1; dy++)
      {
        T nw = {points[i].x + dx, points[i].y + dy};
        if (!w.count(nw))
        {
          int gunoi = get_root(nw);
        }
      }
    }
  }

  assert(!ids.empty());
  ext_tag[get_root(ids.begin()->first)] = 1;

  for (auto &iter : ids)
  {
    T guy = iter.first;
    for (int k = 0; k < 4; k++)
    {
      int dx = dirx[k];
      int dy = diry[k];
      T nw = {guy.x + dx, guy.y + dy};
      if (ids.count(nw))
      {
        join(guy, nw);
      }
    }
  }

  for (auto &iter : ids)
  {
    T guy = iter.first;
  }



  cout << "YES\n";
  /*for (auto &it : ids)
  {
    cout << it.first.x << " " << it.first.y << " " << "P" << it.second << "\n";
  }*/

  for (int step = n; step >= 1; step--)
  {
    for (int i = n; i >= 1; i--)
    {
      if (ales_deja[i])
      {
        continue;
      }
      bool has_access = 0;
      for (int k = 0; k < 4; k++)
      {
        int dx = dirx[k];
        int dy = diry[k];
        T nw = {points[i].x + dx, points[i].y + dy};
        if (w.count(nw))
        {
          int j = w[nw];
          if (ales_deja[j] == 0)
          {
            continue;
          }
        }
        ///cout << " > " << nw.x << " " << nw.y << "\n";
        assert(ids.count(nw));
        has_access |= (ext_tag[get_root(nw)]);
      }
      if (has_access)
      {
        ales_deja[i] = 1;
        if (sanity_check() == 0)
        {
          ales_deja[i] = 0;
          continue;
        }
        int gunoi = get_root(points[i]);
        solution[step] = i;
        break;
      }
    }
    assert(solution[step] != 0);
  }
  for (int i = 1; i <= n; i++)
  {
    cout << solution[i] << "\n";
  }
  return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:164:15: warning: unused variable 'gunoi' [-Wunused-variable]
  164 |           int gunoi = get_root(nw);
      |               ^~~~~
skyscrapers.cpp:190:7: warning: variable 'guy' set but not used [-Wunused-but-set-variable]
  190 |     T guy = iter.first;
      |       ^~~
skyscrapers.cpp:235:13: warning: unused variable 'gunoi' [-Wunused-variable]
  235 |         int gunoi = get_root(points[i]);
      |             ^~~~~
skyscrapers.cpp:91:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 12
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19