Submission #252335

#	Time	Username	Problem	Language	Result	Execution time	Memory
252335		paradox	Ideal city (IOI12_city)	C++17	32 / 100	130 ms	632 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45