Submission #667997

#	Time	Username	Problem	Language	Result	Execution time	Memory
667997		600Mihnea	Adriatic (CEOI13_adriatic)	C++17	0 / 100	2093 ms	10496 KiB

adriatic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 250000 + 7;
const int A = 2500 + 7;
int n;
int r[N];
int c[N];
vector<int> g[N];
int d[N];

bool in_one_step(int a, int b)
{
  return (r[a] < r[b] && c[a] < c[b]) || (r[a] > r[b] && c[a] > c[b]);
}

void addEdge(int a, int b)
{
  g[a].push_back(b);
  g[b].push_back(a);
}

int main()
{
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#endif // ONPC

#ifndef ONPC
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> r[i] >> c[i];
  }
  for (int i = 1; i <= n; i++)
  {
    int x0 = -1, x1 = -1, x2 = -1, x3 = -1;
    for (int j = 1; j <= n; j++)
    {
      if (i != j && in_one_step(i, j))
      {
        if (x0 == -1)
        {
          x0 = x1 = x2 = x3 = j;
          continue;
        }

        if (c[j] < c[x0]) x0 = j;
        if (c[j] > c[x1]) x1 = j;
        if (r[j] < r[x2]) x2 = j;
        if (r[j] > r[x3]) x3 = j;
      }
    }
    set<int> s;
    for (auto &v : {x0, x1, x2, x3})
    {
      if (v != -1)
      {
        s.insert(v);
      }
    }
    for (auto &x : s)
    {
      addEdge(i, x);
    }
  }

  for (int s = 1; s <= n; s++)
  {
    for (int i = 1; i <= n; i++)
    {
      d[i] = -1;
    }
    queue<int> q;
    q.push(s);
    d[s] = 0;
    ll sum = 0;
    while (!q.empty())
    {
      int a = q.front();
      q.pop();
      sum += d[a];
      for (auto &b : g[a])
      {
        if (d[b] == -1)
        {
          q.push(b);
          d[b] = 1 + d[a];
        }
      }
    }
    cout << sum << "\n";
  }

  return 0;
}
/**
**/

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20