oj.uz

Submission #966310

# Submission time Handle Problem Language Result Execution time Memory
966310 2024-04-19T16:51:08 Z AkibAzmain Fountain Parks (IOI21_parks) C++17
0 / 100
 0 ms 348 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -