oj.uz

Submission #667996

# Submission time Handle Problem Language Result Execution time Memory
667996 2022-12-02T13:58:48 Z 600Mihnea Adriatic (CEOI13_adriatic) C++17
25 / 100
 2000 ms 262144 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++)
  {
    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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Output is correct
2 Correct 4 ms 6228 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 5 ms 6228 KB Output is correct
5 Correct 4 ms 6212 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 7584 KB Output is correct
2 Execution timed out 2079 ms 19252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 15580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2025 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1258 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -