Submission #966310

#	Time	Username	Problem	Language	Result	Execution time	Memory
966310		AkibAzmain	Fountain Parks (IOI21_parks)	C++17	0 / 100	0 ms	348 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
    build({}, {}, {}, {});
    return 1;
  }
  map < pair < int, int >, int > a;
  map < pair < int, int >, pair < int, pair < int, int > > > dsu;
  for (int i = 0; i < x.size (); ++i)
    {
      pair < int, int > p = { x[i], y[i] };
      a[p] = i;
      dsu[p] = { 1, p };
    }
  auto ddr = [&] (pair < int, int > x)
  {
    while (dsu[x].first == -1) x = dsu[x].second;
    return x;
  };
  auto dj = [&] (pair < int, int > x, pair < int, int > y)
  {
    x = ddr (x);
    y = ddr (y);
    if (dsu[y] > dsu[x]) swap (x, y);
    dsu[x].first += dsu[y].first;
    dsu[y] = { -1, x };
  };
  map < pair < pair < int, int >, int >, pair < int, int > > rm;
  for (auto p : a)
    {
      auto q = p.first;
      q.first -= 2;
      if (a.count (q))
        {
          dj (p.first, q);
          rm[{ p.first, 1 }] = { p.second, a[q] };
        }
    }
  for (auto p : a)
    {
      auto q = p.first;
      q.second -= 2;
      if (a.count (q) && ddr (p.first) != ddr (q))
        {
          dj (p.first, q);
          rm[{ p.first, 0 }] = { p.second, a[q] };
        }
    }
  map < pair < int, int >, int > bp;
  vector < int > u, v, g, h;
  for (auto x : rm)
    {
      auto p = x.first.first;
      auto d = x.first.second;
      if (d == 1)
        {
          p.first -= 1;
          p.second -= 1;
          if (bp.count (p)) p.second += 2;
          if (bp.count (p)) return 0;
          bp[p] = 1;
        }
      else
        {
          p.second -= 1;
          p.first -= 1;
          if (bp.count (p)) p.first += 2;
          if (bp.count (p)) return 0;
          bp[p] = 1;
        }
      u.push_back (x.second.first);
      v.push_back (x.second.second);
      g.push_back (p.first);
      h.push_back (p.second);
    }
  build (u, v, g, h);
  return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:13:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for (int i = 0; i < x.size (); ++i)
      |                   ~~^~~~~~~~~~~

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