oj.uz

Submission #440005

# Submission time Handle Problem Language Result Execution time Memory
440005 2021-07-01T11:39:26 Z prvocislo Ideal city (IOI12_city) C++17
100 / 100
 173 ms 16636 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int mod = 1e9, maxn = 1e5 + 5;
void upd(int &a, const int &b) { a = (a + b) % mod; }
int add(const int &a, const int &b) { return (a + b) % mod; }
int mul(const int &a, const int &b) { return (a * 1ll * b) % (ll)mod; }
vector<int> g[maxn];
int sz[maxn];
struct bod { int x, y; };
bool cmp(const bod &a, const bod &b) { return (a.x == b.x) ? a.y < b.y : a.x < b.x; }
int ans = 0, n;
void dfs(int u, int p = -1)
{
  for (int v : g[u]) if (v != p) dfs(v, u), sz[u] += sz[v];
  upd(ans, mul(sz[u], n - sz[u]));
}
void calculate_x_dist(vector<bod> v)
{
  for (int i = 0; i < n; i++) g[i].clear(), sz[i] = 0;
  map<pair<int, int>, int> m;
  set<pair<int, int> > e;
  sort(v.begin(), v.end(), cmp);
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    if (i && (v[i-1].x != v[i].x || v[i-1].y+1 != v[i].y)) cnt++;
    m[{v[i].x, v[i].y}] = cnt;
    sz[cnt]++;
    if (m.count({v[i].x-1, v[i].y})) e.insert({m[{v[i].x-1, v[i].y}], cnt});
  }
  for (pair<int, int> i : e) g[i.first].push_back(i.second), g[i.second].push_back(i.first);
  dfs(0);
}
int DistanceSum(int N, int *x, int *y) 
{
  n = N; vector<bod> v;
  for (int i = 0; i < n; i++) v.push_back({x[i], y[i]}); 
  calculate_x_dist(v);
  for (int i = 0; i < n; i++) swap(v[i].x, v[i].y);
  calculate_x_dist(v);
  return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 3 ms 2764 KB Output is correct
3 Correct 4 ms 2788 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 5 ms 2892 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 5 ms 2892 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct
9 Correct 5 ms 2764 KB Output is correct
10 Correct 5 ms 2892 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4552 KB Output is correct
2 Correct 25 ms 4552 KB Output is correct
3 Correct 61 ms 7232 KB Output is correct
4 Correct 65 ms 7352 KB Output is correct
5 Correct 154 ms 11712 KB Output is correct
6 Correct 153 ms 11840 KB Output is correct
7 Correct 130 ms 11996 KB Output is correct
8 Correct 135 ms 11676 KB Output is correct
9 Correct 159 ms 12108 KB Output is correct
10 Correct 154 ms 16636 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5112 KB Output is correct
2 Correct 35 ms 5144 KB Output is correct
3 Correct 74 ms 9148 KB Output is correct
4 Correct 71 ms 8644 KB Output is correct
5 Correct 155 ms 15792 KB Output is correct
6 Correct 151 ms 13844 KB Output is correct
7 Correct 173 ms 15892 KB Output is correct
8 Correct 139 ms 13896 KB Output is correct
9 Correct 141 ms 13424 KB Output is correct
10 Correct 131 ms 13376 KB Output is correct