oj.uz

Submission #230534

# Submission time Handle Problem Language Result Execution time Memory
230534 2020-05-10T10:26:02 Z quocnguyen1012 Ideal city (IOI12_city) C++14
100 / 100
 141 ms 16996 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5, mod = 1e9;

vector<int> adj[maxn];
int sz[maxn], id[maxn], N, n;
int ans;

void dfs(int u, int p = -1)
{
  for(int v : adj[u]) if(v != p){
    dfs(v, u);
    ans += 1ll * (N - sz[v]) * sz[v] % mod;
    ans %= mod;
    sz[u] += sz[v];
  }
}

void solve(int X[], int Y[])
{
  memset(id, 0, sizeof id); memset(sz, 0, sizeof sz);
  for(int i = 0; i < N; ++i)
    adj[i].clear();
  vector<ii> vec;
  for(int i = 0; i < N; ++i)
    vec.eb(X[i], Y[i]);
  sort(vec.begin(), vec.end());

  map<ii, int> ma;
  n = 0;
  for(int i = 0; i < N; ++i){
    ma[vec[i]] = i;
    if(i == 0 || vec[i - 1].fi != vec[i].fi || vec[i - 1].se + 1 != vec[i].se)
      id[i] = ++n;
    else
      id[i] = id[i - 1];
    ++sz[id[i]];
    if(ma.count(mp(vec[i].fi - 1, vec[i].se))){
      int v = id[ma[mp(vec[i].fi - 1, vec[i].se)]];
      adj[id[i]].eb(v); adj[v].eb(id[i]);
    }
  }
  for(int i = 1; i <= n; ++i){
    sort(adj[i].begin(), adj[i].end());
    adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
  }
  dfs(1);
}

int DistanceSum(int _n, int X[], int Y[])
{
  N = _n;
  solve(X, Y); solve(Y, X);
  return ans;
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int _N; cin >> _N;
  int X[_N], Y[_N];
  for(int i = 0; i < _N; ++i){
    cin >> X[i] >> Y[i];
  }
  cout << DistanceSum(_N, X, Y);
}
#endif

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5724 KB Output is correct
2 Correct 27 ms 5724 KB Output is correct
3 Correct 62 ms 8884 KB Output is correct
4 Correct 64 ms 8940 KB Output is correct
5 Correct 124 ms 14432 KB Output is correct
6 Correct 125 ms 14684 KB Output is correct
7 Correct 132 ms 14684 KB Output is correct
8 Correct 125 ms 14456 KB Output is correct
9 Correct 119 ms 14308 KB Output is correct
10 Correct 126 ms 16996 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5852 KB Output is correct
2 Correct 30 ms 5852 KB Output is correct
3 Correct 69 ms 9068 KB Output is correct
4 Correct 65 ms 9068 KB Output is correct
5 Correct 141 ms 14688 KB Output is correct
6 Correct 134 ms 14684 KB Output is correct
7 Correct 141 ms 14868 KB Output is correct
8 Correct 138 ms 14560 KB Output is correct
9 Correct 136 ms 14500 KB Output is correct
10 Correct 131 ms 14432 KB Output is correct