oj.uz

답안 #667997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
667997 2022-12-02T14:00:52 Z 600Mihnea 섬 항해 (CEOI13_adriatic) C++17
0 / 100
 2000 ms 10496 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 6304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 847 ms 6532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2067 ms 7504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2093 ms 10496 KB Time limit exceeded
2 Halted 0 ms 0 KB -