oj.uz

답안 #371534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371534 2021-02-26T20:53:00 Z WLZ 이상적인 도시 (IOI12_city) C++14
100 / 100
 87 ms 11844 KB 
#include <bits/stdc++.h>
using namespace std;

const int MOD = (int) 1e9;

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

int mul(int a, int b) {
  return (long long) a * b % MOD;
}

void dfs(int u, const vector< vector<int> > &g, vector<int> &p, vector<int> &cnt) {
  for (auto& v : g[u]) {
    if (v != p[u]) {
      p[v] = u;
      dfs(v, g, p, cnt);
      cnt[u] += cnt[v];
    }
  }
}

int solve(vector< pair<int, int> > v) {
  int n = (int) v.size();
  sort(v.begin(), v.end());
  vector<int> group(n), cnt(n, 0);
  cnt[0] = 1;
  group[0] = 0;
  for (int i = 1; i < n; i++) {
    group[i] = group[i - 1];
    if (v[i].first != v[i - 1].first || v[i].second != v[i - 1].second + 1) group[i]++;
    cnt[group[i]]++;
  }
  map<int, vector<int> > mp;
  for (int i = 0; i < n; i++) mp[v[i].second].push_back(i);  
  vector< pair<int, int> > edges;
  for (auto& p : mp) {
    for (int i = 1; i < (int) p.second.size(); i++) {
      if (v[p.second[i]].first == v[p.second[i - 1]].first + 1) edges.push_back({group[p.second[i - 1]], group[p.second[i]]});
    }
  }
  sort(edges.begin(), edges.end());
  edges.erase(unique(edges.begin(), edges.end()), edges.end());
  vector< vector<int> > g(group[n - 1] + 1);
  for (auto& e : edges) {
    g[e.first].push_back(e.second);
    g[e.second].push_back(e.first);
  }
  vector<int> p((int) g.size(), -1);
  dfs(0, g, p, cnt);
  int ans = 0;
  for (int i = 1; i <= group[n - 1]; i++) {
    ans = add(ans, mul(cnt[i], n - cnt[i]));
  }
  return ans;
}

int DistanceSum(int N, int *X, int *Y) {
  vector< pair<int, int> > vertical, horizontal;
  for (int i = 0; i < N; i++) {
    horizontal.push_back({X[i], Y[i]});
    vertical.push_back({Y[i], X[i]});
  }
  return add(solve(horizontal), solve(vertical));
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2044 KB Output is correct
2 Correct 13 ms 2044 KB Output is correct
3 Correct 33 ms 4596 KB Output is correct
4 Correct 33 ms 4452 KB Output is correct
5 Correct 67 ms 8392 KB Output is correct
6 Correct 66 ms 8532 KB Output is correct
7 Correct 69 ms 8660 KB Output is correct
8 Correct 66 ms 8520 KB Output is correct
9 Correct 68 ms 8572 KB Output is correct
10 Correct 87 ms 11844 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2288 KB Output is correct
2 Correct 16 ms 2192 KB Output is correct
3 Correct 46 ms 4876 KB Output is correct
4 Correct 40 ms 4636 KB Output is correct
5 Correct 87 ms 9548 KB Output is correct
6 Correct 80 ms 8632 KB Output is correct
7 Correct 86 ms 9600 KB Output is correct
8 Correct 80 ms 8572 KB Output is correct
9 Correct 76 ms 8360 KB Output is correct
10 Correct 78 ms 8352 KB Output is correct