oj.uz

답안 #516154

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516154 2022-01-20T13:12:39 Z 600Mihnea 이상적인 도시 (IOI12_city) C++17
100 / 100
 39 ms 10240 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 1e5 + 7;
const int M = (int) 1e9;

int add(int a, int b) {
  a += b;
  if (a >= M) a -= M;
  if (a < 0) a -= M;
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int a, int b) {
  a = a * (ll) b % M;
}

class Segment {
private:
public:
  int l, r, id;
  Segment(int l, int r, int id) :
    l(l),
    r(r),
    id(id) {
  }
};

vector<int> g[N];
vector<Segment> segs[N];

void addEdge(int a, int b) {
  g[a].push_back(b);
  g[b].push_back(a);
}

int sum[N], T;

void dfs1(int a, int p = -1) {
  for (auto &b : g[a]) {
    if (b == p) continue;
    dfs1(b, a);
    sum[a] += sum[b];
  }
}

void dfs2(int &sol, int a, int p = -1) {
  for (auto &b : g[a]) {
    if (b == p) continue;
    dfs2(sol, b, a);
    addup(sol, mul(sum[b], T - sum[b]));
  }
}

int compute(int n, int *x, int *y) {
  T = n;
  int sol = 0;
  for (int i = 0; i < n; i++) g[i].clear(), segs[i].clear();
  for (int i = 0; i < n; i++) g[x[i]].push_back(y[i]);
  int id = 0;
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end());
    int l = 0, r;
    while (l < (int) g[i].size()) {
      r = l;
      while (r + 1 < (int) g[i].size() && g[i][r + 1] == g[i][r] + 1) r++;
      sum[id] = r - l + 1;
      segs[i].push_back({g[i][l], g[i][r], id++});

      l = r + 1;
    }
  }
  for (int i = 0; i < n; i++) g[i].clear();
  for (int i = 1; i < n; i++) {
    /// add the edges!
    int ant_p = 0;
    for (auto &seg : segs[i]) {
      while (true) {
        if (ant_p == (int) segs[i - 1].size()) break;
        if (segs[i - 1][ant_p].r < seg.l) ant_p++;
        else break;
      }
      int first_good = ant_p;
      while (true) {
        if (ant_p == (int) segs[i - 1].size()) break;
        if (segs[i - 1][ant_p].l > seg.r) break;
        bool notisect = (segs[i - 1][ant_p].r < seg.l || seg.r < segs[i - 1][ant_p].l);
        if (notisect) {
          assert(0);
        }
        addEdge(segs[i - 1][ant_p].id, seg.id);
        ant_p++;
      }
      ant_p = first_good;
    }
  }
  n = id;
  dfs1(0);
  dfs2(sol, 0);
  return sol;
}

int DistanceSum(int n, int *x, int *y) {
  {
    int __x = x[0], __y = y[0];
    for (int i = 1; i < n; i++) {
      __x = min(__x, x[i]);
      __y = min(__y, y[i]);
    }
    for (int i = 0; i < n; i++) {
      x[i] -= __x;
      y[i] -= __y;
    }
    for (int i = 0; i < n; i++) {
      assert(0 <= x[i] && x[i] < n);
      assert(0 <= y[i] && y[i] < n);
    }
  }

  return add(compute(n, x, y), compute(n, y, x));
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Correct 2 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 2 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 5044 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5452 KB Output is correct
2 Correct 8 ms 5452 KB Output is correct
3 Correct 14 ms 5836 KB Output is correct
4 Correct 15 ms 6092 KB Output is correct
5 Correct 28 ms 6604 KB Output is correct
6 Correct 28 ms 7240 KB Output is correct
7 Correct 26 ms 6988 KB Output is correct
8 Correct 29 ms 6636 KB Output is correct
9 Correct 28 ms 7116 KB Output is correct
10 Correct 37 ms 10240 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5836 KB Output is correct
2 Correct 13 ms 5776 KB Output is correct
3 Correct 20 ms 7192 KB Output is correct
4 Correct 17 ms 6732 KB Output is correct
5 Correct 39 ms 9156 KB Output is correct
6 Correct 30 ms 7636 KB Output is correct
7 Correct 39 ms 8908 KB Output is correct
8 Correct 31 ms 7768 KB Output is correct
9 Correct 30 ms 7044 KB Output is correct
10 Correct 32 ms 7244 KB Output is correct