Submission #667996

#	Time	Username	Problem	Language	Result	Execution time	Memory
667996		600Mihnea	Adriatic (CEOI13_adriatic)	C++17	25 / 100	2079 ms	262144 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++)
  {
    for (int j = 1; j <= n; j++)
    {
      if (i != j && in_one_step(i, j))
      {
        addEdge(i, j);
      }
    }
  }

  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: 25 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20