oj.uz

Submission #252335

# Submission time Handle Problem Language Result Execution time Memory
252335 2020-07-25T10:04:35 Z paradox Ideal city (IOI12_city) C++17
32 / 100
 130 ms 632 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
using namespace std;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define vi vector<int>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
typedef long long ll;
typedef short inth;
 
const int N = 2e3;
const int M = N + 7;
const int MOD = 1e9;
const ll INF = 1e16 + 17;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool areAdjacent(int i, int j, int x, int y) {
  for (int id = 0; id < 4; ++id)
    if (i + dx[id] == x && j + dy[id] == y)
      return true;
  return false;
}

vi edges[M];
int d[M];

int sum(int a, int b) {
  return (a + b >= MOD ? a + b - MOD : a + b);
}

int solveSub1and2(int n, int *x, int *y) {
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (areAdjacent(x[i], y[i], x[j], y[j])) {
        edges[i].pb(j);
        edges[j].pb(i);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    memset(d, -1, sizeof d);
    d[i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      int v = q.front();
      if (v > i)
        ans = sum(ans, d[v]);
      q.pop();
      for (int to : edges[v]) {
        if (d[to] == -1) {
          d[to] = d[v] + 1;
          q.push(to);
        }
      }
    }
  }
  return ans;
}

int solveSub3(int n, int *x, int *y) {
  return 0;
}

int DistanceSum(int n, int *x, int *y) {
  if (n <= 2000)
    return solveSub1and2(n, x, y);
  else
    return solveSub3(n, x, y);
  return n;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 384 KB Output is correct
2 Correct 30 ms 384 KB Output is correct
3 Correct 66 ms 384 KB Output is correct
4 Correct 71 ms 384 KB Output is correct
5 Correct 116 ms 632 KB Output is correct
6 Correct 130 ms 632 KB Output is correct
7 Correct 127 ms 512 KB Output is correct
8 Correct 129 ms 512 KB Output is correct
9 Correct 128 ms 512 KB Output is correct
10 Correct 124 ms 632 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -